摘要
遗传算法作为一种非确定性的拟生态随机优化算法在过去20年中得到了广泛的应用。由于其具有不依赖于问题模型的特性、全局最优性、隐含并行性等特点,正越来越激起人们研究与应用的兴趣。
多目标决策问题是从实际应用中产生的,它不论在经济、军事还是高科技领域都有着重要的研究价值。尽管多年来多目标决策问题已有许多求解方法,然而最近十几年来遗传算法已逐渐发展成为解决多目标决策问题的理想方法。但在实际应用中,人们常常发现,遗传算法会收敛到局部最优而不再进化,或者是群体中不能再产生性能超过父代的后代,群体中的各个个体之间非常相似即出现未成熟收敛现象。
本文介绍了遗传算法和多目标决策的原理和方法,并围绕遗传算法中的早熟问题对遗传算法进行改进。基于配对策略,为了维持群体的多样性,该文设计的防乱伦遗传算法是有目的地选择配对个体,去除相似个体。然后通过三次试验对该改进算法进行验证,试验结果表明INGA能很好的摆脱早熟,并能搜索到最优值,且搜索的效率也很高。
另外,本文以贵州省某药厂ERP系统的生产计划为例,提出多目标生产计划模型,并将改进的遗传算法应用于求解此多目标决策模型,从而使药厂摆脱了以往手工制定生产计划的过程,根据决策者的偏好,智能决策出客观、合理的生产计划。
As an uncertain stochastic optimal algorithm, GA is applied in kinds of fields in the past 20 years. And because of its independence, global optimization and implicit parallelism, GA is developed and applied by more and more people.
Arising from practical problems, Multi-objective Decision-making Problems (MDPS) plays a significant role in economy, military and other high-tech research fields. Although the approaches for solving MDPS have been available for many years, genetic algorithm have been developed to be ideal techniques for solving MDPS. But in practical application, people discover frequently that the genetic algorithm can converge on the local optimization and no longer evolve, or cannot have the descendant that it is capability cannot surpass it is father is in colony. In colony, each individual is extremely similar and appears the premature convergence phenomenon.
In this paper, the elementary theory and methods of genetic algorithm and multi-objective decision-making is introduced. Some improvement of GA on the premature convergence is presented. The improved GA which was designed by this article purposefully chooses mating individual and eliminates similar individual based on mating strategies and maintaining population diversity. Then we test the INGA through two typical functions. The test result indicated that the INGA can get rid of premature convergence well and search the optimal value, the searching efficiency is very well.
In addition, we take a ERP productive plan of pharmaceutical factory in the Guizhou Province as an example and propose a multi-objective productive plan model, then apply the improved genetic algorithm to solving it which make the pharmaceutical factory getting rid of the former productive plan process by hand-made. In this way, the impersonal and reasonable productive plan can be decided intelligently by favorite of decision-making person.
引文
[1] 于群,曹娜.微机保护算法在矿井电动机综合保护中的应用.煤炭科学技术,2002 Vol.30 No.8
[2] 王小平,曹立明著.遗传算法—理论、应用与软件实现[M].西安:西安交通大学出版社,2002
[3] 王征应、石冰心.基于启发式遗传算法的QoS组播路由问题求解.计算机学报,2001,24(1):55~61.
[4] 文瑛,蒋华,雷鸿.一类基于混合遗传算法的多目标优化.广西师范学院学报,2003.3 Vol.12 No.1
[5] 艾丽蓉,何华灿.遗传算法综述.计算机应用研究,1997,4:3-6
[6] 玄广男,程润伟.遗传算法与工程设计.北京:科学出版社 2000.1
[7] 吉根林.遗传算法研究综述[J].计算机应用与软件,2004,21(2):69-73.
[8] 李满林,杜雷,闻英友,王玉娜,王光兴.多目标优化遗传算法在移动网络规划中的应用[J].控制与决策,2003,18(4):441~444.
[9] 刘大有,卢奕南,王飞.遗传程序设计方法.计算机研究与发展,2001,38(2):213-222.
[10] 刘金芳,杨秀芳,高霞.遗传算法的早熟问题[J].内蒙古科技与经济,2005:81
[11] 刘勇,康立山,陈屏.非数值并行算法(第二册).北京:科学出版社,2003.
[12] 陈国良等.遗传算法的理论及其应用.北京:人民邮电出版社,1996.
[13] 张国胜,李以农,李松森.一种改进的浮点数编码遗传算法及其应用[J].重庆大学学报(自然科学版),2005,28(5):5-7
[14] 张潜,高立群,胡祥培,吴畏.集成化物流中的定位—配给问题的启发式算法.控制与决策,2003 Vol.18 No.4
[15] 林磊,王晓龙,刘家锋.基于遗传算法的手写体汉字识别系统优化方法的研究.计算机研究与发展,2001,38(6):658~661.
[16] 杨金明,吴捷,钟丹虹.多目标优化问题中一种改进的遗传算法.华南理大学学报,2001 Vol.29 No.12
[17] 周远晖,陆玉昌,石纯一.基于克服过早收敛的自适应并行遗传算法[J].清华大学学报(自然科学版),1998,38(3):93-95
[18] 周明,孙树栋.遗传算法原理及应用.北京:国防工业出版社,1999.
[19] 周明,孙树栋,彭炎午.用遗传算法规划移动机器人路径.西北工业大学学报,1998,16(4).
[20] 周明,孙树栋,彭炎午.基于遗传模拟退火算法的机器人路径规划.航空学报,1998,19(1):18~120.
[21] 赵河.ERP在我国的发展现状及发展趋势[J].电脑知识与技术,2005.6
[22] 姚伟,谭惠丰,杜星文.遗传算法在轮胎结构多目标优化设计中的应用.复合材料学报,2002 Vol.19 No.3
[23] 贾兆红.遗传算法及其在知识发现和范例推理中的应用研究[D].安徽:安徽大学,2003.
[24] 钱志勤、滕弘飞、孙治国.人机交互的遗传算法及其在约束布局优化中的应用.计算机学报,2001,24(5):553~558.
[25] 涂雪珠.遗传算法在多目标优化中的应用[D].福州大学,2004
[26] 席裕庚,柴天佑,郓为民.遗传算法综述.控制理论与应用,1996,13(6):697-708.
[27] 梁武科,罗兴琦,冯建军.遗传算法在离心泵叶片优化设计中的应用.水利学报,2003 No.4
[28] 覃俊,康立山.基于遗传算法求解多目标优化问题Pareto前沿.计算机工程与应用,2003 Vol.39 No.23
[29] 谢涛,陈火旺.多目标优化与决策问题的演化算法.中国工程科学,2002年第4卷第2期
[30] 谢涛,陈火旺,康立山,多目标优化与决策问题的演化算法.计算机学报,2003.8
[31] 雷英杰,张善文,李续武,周创明编著.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2004
[32] 解可新,韩立兴,林友联.最优化方法[M].天津:天津大学出版社,1997
[33] 潘正君,康立山.演化计算.清华大学出版社1998.7
[34] Bagley J. D.. The Behavior of Adaptive Systems Which Employ Genetic and Correlation Algorithms. Dissertation Abstracts International, 1967,28(12).
[35] Bremermann, H. J.. Optimization Through Evolution and Recombination. in Self-Organizing Systems, Yovits, M.C., Jacobi, G.T. and Goldstine, G.D.Eds., Spartan Books, 1962, 93-106
[36] C H Tseng, T W Lu. Minimax multiobjective optimization in structural design[J].International Journal for Numerical Methods in Engineering, 1990.30:1213-1228
[37] C M Fonseca, P J Fleming. Genetic algorithms for mufti-objective optimization: formulation Conference on discussion and generation[A].Proceedings of the fifth International Genetic Algorithms[C].California, University of Illinois at Urbana Champaign, Morgan Kaufman Publishers,1993. 416-423
[38] David A. Van Veldhuizeu. Grav B. Lamont. Multiobjective evOolutionaw algorithms analyzing the state-of-the-art[J].Evolutionary Computation.8(2):125-147.2000
[39] Davis L. D.. Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold, 1991
[40] Davis, L.. Adapting Operater Probabilities in Genetic Algorithms. Proc. 3rd Genetic Algorithm, 1989, 61-69
[41] De Jong K.A.. An Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD Dissertection, University of Michigan,No.76-9381,1975
[42] Dev,K.,Optimization for Engineering Design: Algorithms and Examples, Prentice-Hall, New Delhi, 1995
[43] F. Kursawe. A variant of evolution strategies for vector optimization. In H. P. Schwefel and R. Manner, editors, Parallel Problem Solving from Nature. 1st Workshop, PPSN Ⅰ, volume 496 of Lecture Notes in Computer Science, Berlin, Germany, Springer-Verlag. Oct 1991:93-197
[44] Flavio Baita, Francesco Mason, Carlo Poloni, and Walter Ukovich. Genetic algorithm with redundancies for the vehicle scheduling problem [A].BiethahnJ, Nissen V. Evolutionary Algorithms in Management Applications [M].Berlin: Springer Verlag. 1995.341-353
[45] Foguel L. J.. On the Organization of Intellect. Doctoral Dissertation, UCLA, 1964
[46] Foguel L. J., Owens A. J., Walsh M. J.. Artificial Intelligence through simulated evolution. New York: John Wiley, 1966
[47] Goldberg D.E..Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison Wesley, 1989
[48] Goldberg, D. E.Simple Genetic Algorithms and the Minimal Deceptive Problem. In L.Davis (Ed.), Genetic Algorithms and Simulated Annealing, London Pitman,1987,74—78
[49] Hajela P, Lin C.Y, Genetic search strategics in multi-criterion optimal design.Structural Optimization, 1992 4: 99-107
[50] Holland, J. H. A new kind of turnpike theorem. Bulletin of the American Mathematical Society 75 (1969), pp. 297-314.
[51] Holland, J. H..Adaptation in Natural and Artificial Systems, 1st ed., 1975. 2nd ed., Cambridge, MA: MIT press, 1992
[52] Holland, J. H. .Concerning Efficient Adaptive Systems. In Yovits, M. C.,Eds., Self-Organizing Systems, 1962,215-230
[53] Holland J.H., Reitman J.S.. Cognitive Systems Based on Adaptive Algorithms. In: Waterman D.A.& Hayes-Roth F. Eds. Pattern Directed Inference Systems, New York: Academic Press,1978,313-329
[54] Holland, J. H. Outline for a logical theory of adaptive systems. Journal of the Association for Computing Machinery, 3 (1962), pp.297-314.
[55] Hom J, Nafpliotis N, Goldberg D.E. A aiched Pareto genetic algorithm for multiobjective optimization. In: Proceeding of 1St IEEE conference on Evolutionary Computation. IEEE World Conference on Computational Computation, Piscataway, NJ. 1994,1:82-87
[56] J. Horn and N. Nafpliots. Multi-objective optimization using the Riched Pareto genetic algorithm[R].Technical Report IlliGAL Report 93005, University of Illinois at Urbana-Champaign, Urbana, Illinois, USA,1993
[57] Koza, J. R..Hierarchical Genetic Algorithms Operation on Populations of Computer Programs. Proc. of 11th Int'I Joint Conf. on Artificial Intelligence, 1989
[58] Koza, J. R..Genetic Programming. Cambridge, MA:MIT Preys, 1992
[59] Koza, J. R.. Genetic Programming on the Programming of Computers by Means of Natural Selection. MIT press, 1992
[60] Koza J. R.. Genetic Programming Ⅱ ,Automatic Discovery of Reusable programs. MIT press,1994
[61] Krishnaknmar K.. Micro-genetic Algorithms for Stationary and Non-Stationary Function Optimization. SPIE In-teleigent Control and Adaptive Systems, 1989,1196:289-296
[62] M. P. Fourman. Proceedings Algorithms[C].of Compaction of symbolic layout the First International using genetic algorithms[A]. Conference on Genetic Lawrence Erlbaum, 1985. 141—153
[63] Michalewicz Z.,A Modified Genetic Algorithm for Optimal Control Prolylems. Computer Math.Application,1992,23(12):83~94.
[64] Michalewicz Z. Genetic Algorithms +Data Structures=Evolution programs [M]. 3rd edition, New York: Springer-verlag,1996
[65] P. B.Wienke, C. Lucasius, G. Kateman. Multicriteria target vector optimation of analytical. procedures using a genetic algorithm[J].Analytical Chimical Acta,1992. 265 (2):211-225
[66] R. C. Purshouse and P. J. Fleming. Elitism, Sharing and Ranking Choices in Evolutionary Multi-Criterion Optimization, Technical Report No. 815, Department of Automatic Control and Systems Engineering, University of Sheffield, Sheffield, UK, January 2002
[67] R.Viennet, C.Fontie, Marc I. Multi-criteria optimization using a genetic algorithm for determining a Pareto set[J].International Journal of System Science, 1996. 27 (2):255-260
[68] Ringuest J. L. Multio-bjective optimization: behavior and computational considerations Boston: Kluwer. 1992
[69] Rosenberg R. B. Simulation of genetic populations with biochemical properties. PH. D Dissertation, University of Michigan, 1967.
[70] Schaffer J.D. Multiple objective optimization with vector evaluated genetic algorithm. In: Proceedings of 1st international conference on Genetic algorithms. 1985,93-100
[71] Steuer, R.E., Multiple Criteria Optimization: Theory, Computation, and Application, Wiley, New York, 1986
[72] Sunil Choenni, Design and Implementation of a Genetic—Based Algorithm for Date Mining. In: Proceeding of the 26th VLDB Conference,Cairo,Egypt,2000:33~42.
[73] T K Liu, T.Ishihara, H.Inooka. Multi-objective control systems design by genetic algorithms[A].Proceedings of the 34th Society of International and Control Engineering Annual Conference[C], 1995.1521-1526
[74] Y. Takada, M. Yamamura, S. Kobayashi. An approach to Portfolio selection problems using multi—objective genetic algorithms [A]. proceedings of the 23rd Symposium on Intelligent Systems[C], 1996.103-108
[75] Z. Michalewicz. 演化程序.科学出版社 2000.1
[76] Zitzler E., Thiele L.. Multiobjective evolutionary algorithm: a comparative case study and thestrength pareto approach. IEEE Transactions on Evolutionary Computation. 1999, 3(4): 257-271