遗传算法，选择算子之锦标赛选择（竞赛选择）（选择算子对遗传算法收敛性的影响）

遗传算法，选择算子之锦标赛选择（竞赛选择）（选择算子对遗传算法收敛性的影响）

遗传算法，是最常用的解决优化问题的算法，是最早的群智能算法。遗传算法中主要包括，选择、交叉、变异算子，其中对DNA个体的编码方式分为实数编码和二进制编码等。今日由于学习和工作需要对该算法进行了一些了解，对该算法中常用的竞赛选择方式做如下笔记：

遗传算法中的竞赛选择方式是一种放回抽样，几元竞赛就是一次性在总体中取出几个个体，然后在这些个体中取出最优的个体放入保留到下一代种群的集合中。需要保存多少个体就重复此操作几次。

以下为python2.7写的代码，已经测试过，共两个文件，可以通过修改mycmp.py中的比较函数以适应不同需求。

tournament_selection.py

1 #!/usr/bin/env python 2 #encoding:UTF-8 3 import random 4 import numpy as np 5 from mycmp import mycmp 6 7 """ 8 锦标赛方式选择, 选择出个体编号 9 indicateValueDict {个体索引号：(Value1, Value2), } 10 key为索引号，从0开始。value为元组,一般不超过两个元素。11 12 selectNum 需要选择出的个体个数13 elementNum=2 默认为二元竞赛选择14 """15 def tournament_selection_Dict(indicateValueDict, selectNum, elementNum=2):16 #个体索引列表17 indicateList=range(len(indicateValueDict)) 18 #选择出的个体序号 列表19 remainIndicateList=[]20 21 #构建列表 [(索引号，(Value1, Value2)), ]22 indicateValueList=indicateValueDict.items()23 24 #对列表排序, 排序规则按个人需求定制,修改mycmp即可25 for i in xrange(selectNum):26 tempList=random.sample(indicateValueList, elementNum)27 tempList.sort(cmp=mycmp)28 29 bestIndicate=tempList[0][0]30 remainIndicateList.append(bestIndicate)31 ###返回选择的索引列表32 return remainIndicateList33 34 35 def tournament_selection_Matrix(indicateValueMatrix, selectNum, elementNum=2):36 #个体索引列表37 indicateList=range(indicateValueMatrix.shape[0]) 38 #选择出的个体序号 列表39 remainIndicateList=[]40 41 for i in xrange(selectNum):42 tempList=random.sample(indicateList, elementNum)43 tempMatrix=indicateValueMatrix[tempList, ]44 45 tempMatrixToList=tempMatrix.tolist()46 tempMatrixToList=[(k[0], k[1:])for k in tempMatrixToList]47 tempMatrixToList.sort(mycmp)48 49 remainIndicateList.append(tempMatrixToList[0][0])50 return remainIndicateList51 52 53 def tournament_selection_Dict2(indicateValueDict, selectNum, elementNum=2):54 #个体索引列表55 indicateList=range(len(indicateValueDict)) 56 #选择出的个体序号 列表57 remainIndicateList=[]58 59 #构建列表 [(索引号，(Value1, Value2)), ]60 indicateValueList=indicateValueDict.items()61 62 #对列表排序, 排序规则按个人需求定制,修改mycmp即可63 indicateValueList.sort(cmp=mycmp)64 65 for i in xrange(selectNum):66 tempList=[]67 tempList.extend(random.sample(indicateList, elementNum))68 bestIndicate=indicateValueList[min(tempList)][0]69 remainIndicateList.append(bestIndicate)70 ###返回选择的索引列表71 return remainIndicateList72 73 74 if __name__=="__main__":75 xN=2076 yN=377 selectNum=1078 indicateValueDict={0:[1,2.1], 1:[1,2.2], 2:[1,2.3], 3:[1,2.4], 4:[1,2.5], 5:[1,2.6], 6:[1,2.7], 7:[1,2.8], 8:[1,2.9], 9:[1,3.0], 10:[0,2.1], 11:[0,2.2], 12:[0,2.3], 13:[0,2.4], 14:[0,2.5], 15:[0,2.6], 16:[0,2.7], 17:[0,2.8], 18:[0,2.9], 19:[0,3.0]}79 random.seed(0)80 print tournament_selection_Dict(indicateValueDict, selectNum)81 print '-'*5082 random.seed(0)83 print tournament_selection_Dict2(indicateValueDict, selectNum)84 print '-'*5085 indicateValueMatrix=np.matrix([[0, 1, 2.1], [1, 1, 2.2], [2, 1, 2.3], [3, 1, 2.4], [4, 1, 2.5], [5, 1, 2.6], [6, 1, 2.7], [7, 1, 2.8], [8, 1, 2.9], [9, 1, 3.0], [10, 0, 2.1], [11, 0, 2.2], [12, 0, 2.3], [13, 0, 2.4], [14, 0, 2.5], [15, 0, 2.6], [16, 0, 2.7], [17, 0, 2.8], [18, 0, 2.9], [19, 0, 3.0]])86 random.seed(0)87 print tournament_selection_Matrix(indicateValueMatrix, selectNum)

mycmp.py

1 #!/usr/bin/env python 2 #encoding:UTF-8 3 4 ###列表比较 算子 CMP 5 ### 第一位元素升序， 第二位元素降序 6 def mycmp(left, right): 7 #left 位于列表左的元素， right列表右侧的元素 8 a=left[1] 9 b=right[1]10 11 if a[0]>b[0]:12 return 113 elif a[0]b[1]:18 return -119 else:20 return 021 22 if __name__=="__main__":23 data=[(0, (0, 1)), (1, (1, 0)), (2, (1, 1))]24 data.sort(cmp=mycmp)25 print data

运行效果图：

本程序可以作为单独模块被调用，具体代码地址如下：

https://github.com/guojun007/tournament_selection

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。