模拟退火遗传算法及其在混流装配线设计中的应用
资料包括： 论文(6页5229字)
说明：
摘 要：为克服简单遗传算法局部搜索能力差，容易产生早熟收敛的缺点，将遗传算法和局部搜索能力较强的模拟退火算法相结合，形成模拟退火遗传算法。通过Shaffer’s F6和Rosenbrock两种常用测试函数的测试，表明了模拟退火遗传算法在收敛速度和收敛质量上均优于简单遗传算法。最后将模拟退火遗传算法应用于一个混流装配线的平衡和排序设计的实际问题中，求解结果再次表明模拟退火遗传算法优于简单遗传算法，为求解混流装配线设计问题提供了一种新的算法途径。
关键词：遗传算法；模拟退火算法；混流装配线；平衡和排序
Simulated annealing genetic algorithm and its application in mixed-model assembly line design
Abstract: Simple genetic algorithm has the shortcomings of poor local search ability and premature convergence. To overcome these disadvantages, simulated annealing algorithm which has good local search ability was combined with genetic algorithm to form simulated annealing genetic algorithm. The tests by Shaffer’s F6 and Rosenbrock two commonly used test functions show that simulated annealing genetic algorithm is better than the simple genetic algorithm both in convergence rate and convergence quality. Finally, the simulated annealing genetic algorithm was applied in a practical problem of balancing and sequencing design of mixed-model assembly line, once again, the solution results show that simulated annealing genetic algorithm is better than the simple genetic algorithm. Meanwhile, it provides a new algorithm for solving the problem of mixed-model assembly line design.
Key words: genetic algorithm; simulated annealing algorithm; mixed-model assembly line; balancing and sequencing
0引言
遗传算法最早由美国Michigan大学的John Holland教授提出，是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它不依赖问题的具体模型，把握搜索过程的能力较强。但经验数据表明，简单遗传算法（SGA）局部搜索能力较差，存在早熟收敛和后期收敛速度慢的缺点。模拟退火算法最早由Kirkpatrick等人提出，具有较强的局部搜索能力，能够使搜索过程免于陷入局部最优解。但它不适合搜索整个空间，不能使搜索过程进入最有希望的搜索区域，从而使算法的运行效率不高。如果将遗传算法和模拟退火算法相结合，进行优势互补，则有可能开发出全局和局部搜索能力均较强的模拟退火遗传算法（GSA）。
本文首先将遗传算法和模拟退火算法相结合，形成模拟退火遗传算法；然后，利用Shaffer’s F6和Rosenbrock两种权威测试函数对其进行性能测试，并与简单遗传算法作比较；最后，将模拟退火遗传算法应用于混流装配线的平衡和排序设计这一NP-hard问题中，以最小化闲置与超载时间之和为目标，成功地以较少的代数搜索出较优的平衡和排序结果。
1模拟退火遗传算法
本文以保留最佳个体的简单遗传算法为框架，融入模拟退火算法形成模拟退火遗传算法。整个算法过程由两部分组成，首先通过遗传算法操作产生较优的一代种群，再利用模拟退火操作，对种群中各个个体进行模拟退火，以达到局部寻优的效果。如此循环进行，直至满足收敛准则。具体步骤如下：
Step1: 设置遗传算法各参数值，即种群大小pop_Size，遗传代数gen，交叉概率Pc，变异概率Pm，当前运行代数g=0，及模拟退火初始温度T。
Step2: 随机产生初始种群P(g)，并计算种群中各个体的适应值f(Pi (g))(i=1,2,…,pop_Size)。
Step3: 保留适应值最大的个体。
Step4: 对种群中其余个体进行轮盘赌选择操作；
Step5: 以交叉概率Pc对选择后的种群进行成对交叉操作。
Step6: 以变异概率Pm对交叉后的种群进行变异操作。
Step7: 在变异后的种群中加入Step3中保留的最佳个体，形成新的一代种群,设置g=g+1。
Step8: 计算新一代种群中各个体的适应值f(Pi (g))(i=1,2,…,pop_Size)。
Step9: 对新种群中各个体进行模拟退火操作。第i个个体的操作流程为：（1）设置当前接受次数y=0，总接受次数为Y；（2）对个体Pi (g)产生扰动，生成新个体P’i (g)；（3）计算新个体的适应值f(P’i (g))；（4）利用Metropolis接受准则判断是否接受新个体，即：若f(P’i (g))≧f(Pi (g))，则接受新个体，进行个体替换Pi (g)= P’i (g)，f(Pi (g))= f(P’i (g))，y=y+1；否则，产生[0,1)区间内的随机数rnd，若rnd<exp[(f(P’i (g))- f(Pi (g)))/T]，则接受新个体，进行个体替换Pi (g)= P’i (g)，f(Pi (g))= f(P’i (g))，y=y+1;（5）判断接受次数y是否不小于Y，若是，个体退火结束，否则转（2）。
1 模拟退火遗传算法
2 算法测试
3 算法应用
4 结论
参考文献：
Holland J H. Adaptation in nature and artificial systems[M]. Ann Arbor: The University of Michigan Press, 1975.
Godberg D E. Genetic algorithms in search, Optimization and Machine Learning[M]. Addison-Wesley, New York, 1989.
Kirkpatrick S, Gellatt C D, Vechi M R. Optimization by simulated annealing[J]. Science, 1983, 220:671-680.
雷英杰, 张善文, 李续武等. MATLAB遗传算法工具箱及应用[M]. 西安: 西安电子科技大学出版社, 2005.
A R Rahimi-Vahed，M Rabbani，R Tavakkoli-Moghaddam，et al. A multi-objective scatter search for mixed-model assembly line sequencing problem[J]. Advanced Engineering Informatics，2007，21：85-99.
Moden Y. Toyota Production Systems：An Integrated Approach to Just-In-Time. 2nd ed. Georgia：Industrial Engineering and Management Press[M]，1993.
Yeo Keun Kim, Yong Ju Kim, Yeongho Kim. Genetic algorithms for assembly line balancing with various objectives[J]. Computers & Industrial Engineering, 1996,30(3): 397-409.
宋华明，韩玉启，李如俊. 基于遗传算法的装配线负荷平衡[J].机械设计与制造，2002，(4): 28-30.
Yeo Keun Kim, Chul Ju Hyun, Yeongho Kim. Sequencing in mixed model assembly lines: A genetic algorithm approach[J]. Comput. Ops. Res., 1996,23(12):1131-1145.
作者点评：
本文以保留最佳个体的简单遗传算法为框架，融入了模拟退火算法，形成模拟退火遗传算法。通过Shaffer’s F6和Rosenbrock两种常用测试函数的测试，与保留最佳个体的简单遗传算法进行比较，得出模拟退火算法的融入，使得遗传算法的局部寻优能力大大增强，弥补了简单遗传算法的缺陷，使其搜索效率和质量均得到了提高。采用这种模拟退火遗传算法对一个混流装配线的平衡和排序问题进行求解，给出了混流装配线的平衡和排序设计结果和目标函数的收敛情况。计算表明，模拟退火遗传算法在混流装配线的平衡和排序设计这一实际问题中的应用，仍然保留着较强的局部搜索能力，不易陷入局部最优，最终能够搜索到比简单遗传算法优秀得多的解，为求解混流装配线设计问题提供了一种新的算法途径。