轮盘赌算法

轮盘赌算法

• 
  

  一、基本轮盘选择

• • 代码实现
• 
  

  二、二分搜索轮盘选择

• • 二分查找函数
  • 代码实现
• 
  

  三、随机接受

• • 代码实现
• 
  

  四、可视化

• • 代码实现
  • 补充
  • • 所用到的库如下：

一、基本轮盘选择 代码实现

def basic(series):
    '''
    :param series:the list or tuple
    :return:selected index
    '''
    series_sum = sum(series)
    # generate a random number
    selectPoint = random.uniform(0, series_sum)
    # calculate the index: O(N)
    accumulator = 0.0
    for index, value in enumerate(series):
        accumulator += value
        if accumulator >= selectPoint:
            return index

二、二分搜索轮盘选择 二分查找函数

bisect()，bisect_left()，bisect_right()的使用和其区别。

而bisect()和bisect_right()是等同的，所以下面主要介绍bisect_left()和bisect_right()。

bisect_left(series, x) 
#第一个参数是列表，并且在列表有序的前提下，第二个参数是查找的数，返回值是查找的数的索引。

下面分三种情况来讨论。

1.列表中没有x
此时bisect_left()，bisect_right()的返回值相同,该值是合适的插入点的索引。

#程序代码
import bisect
series = [1,5,9,13,17]
index1 = bisect.bisect(series,7)
index2 = bisect.bisect_left(series,7)
index3 = bisect.bisect_right(series,7)
print("index1 = {},index2 = {},index3 = {}".format(index1,index2,index3))
#运行结果
index1 = 2,index2 = 2,index3 = 2

2.列表中有x且只有一个
此时bisect_left()的返回值是x在序列中的索引，而bisect_right()的返回值是x在序列中的返回值+1。

#程序代码
import bisect
series = [1,5,9,13,17]
index1 = bisect.bisect(series,9)
index2 = bisect.bisect_left(series,9)
index3 = bisect.bisect_right(series,9)
print("index1 = {},index2 = {},index3 = {}".format(index1,index2,index3))
#运行结果
index1 = 3,index2 = 2,index3 = 3

3.列表中有x且有多个
此时bisect_left()的返回值是x在序列中的最小索引，而bisect_right()的返回值是x在序列中的最大索引。

#程序代码
import bisect
series = [1,5,5,5,17]
index1 = bisect.bisect(series,5)
index2 = bisect.bisect_left(series,5)
index3 = bisect.bisect_right(series,5)
print("index1 = {},index2 = {},index3 = {}".format(index1,index2,index3))
#运行结果
index1 = 4,index2 = 1,index3 = 4

代码实现

def bisectSearch(series):
    '''
    Bisecting search roulette wheel selection: O(N + logN)
    :param series: the list or tuple
    :return: selected index
    '''
    series_sum = sum(series)
    # generate a random number
    selectPoint = random.uniform(0, series_sum)
    # calculate the accumulator: O(N)
    accumulator = []
    accsum = 0.0
    for element in series:
        accsum += element
        accumulator.append(accsum)
    return bisect_left(accumulator, selectPoint)   # O(logN)

三、随机接受 代码实现

def stochasticAccept(series):
    '''
    Stochastic Acceptance: O(1) if given the N and maxFit before
    :param series: the list or tuple
    :return: selected index
    '''
    # calculate N and max fitness value
    N = len(series)
    series_max = max(series)
    # select: O(1)
    while True:
        # randomly select an individual with uniform probability
        index = int(N * random.random())
        # with probability wi/wmax to accept the selection
        if random.random() <= series[index] / series_max:
            return index

四、可视化 代码实现

def visual():
    # init number of fitness values
    N = [10, 10**2, 10**3, 10**4, 10**5]
    # calculate average total run time for each algorithm
    times = [[], [], []]
    algos = [basic, bisectSearch, stochasticAccept]
    for n in N:
        fitness = np.random.random((n,))
        for ind, algo in enumerate(algos):
            sample_times = []
            start = timeit.default_timer()
            for _ in range(100):
                algo(fitness)
                sample_times.append(timeit.default_timer() - start)
            times[ind].append(np.array(sample_times).mean())
    # plot the result
    lineStyle = ['b-o', 'g--p', 'r:*']
    algoName = ['basic', 'bisectSearch', 'stochasticAccept']
    for i in range(len(times)):
        plt.loglog(N, times[i], lineStyle[i], label=algoName[i])
    plt.legend(loc=2)
    plt.title('log-log plot of average running time')
    plt.xlabel('N')
    plt.ylabel('Average Running Time')
    plt.grid('on')
    plt.show()

结果如下：

补充 所用到的库如下：

from __future__ import division
import random
from bisect import bisect_left
import numpy as np
import timeit
import matplotlib.pyplot as plt

参考链接：https://github.com/mangwang/PythonForFun/blob/master/rouletteWheelSelection.py