基于和声搜索算法求解组合优化问题 |
|
|
基于和声搜索算法求解组合优化问题
0 引言 当前,论文联盟*演化计算领域新算法不断涌现,继遗传算法(Genetic Algorithm, GA)[1]、蚁群优化(Ant Colony Optimization,ACO)[2]、粒子群优化(Particle Swarm Optimization, PSO)[3]和差分演化(Differential Evolution, DE)[4]之后,又先后出现了混合蛙跳算法(Shuffled Frog.Leaping Algorithm,SFLA)[5,6]、萤火虫算法(Firefly Algorithm, FA)[7]与和声搜索算法(Harmony Search Algorithm, HSA)[8]等多种新型进化算法。其中,HSA是由Geem等[8]于2001年提出的一种新型进化算法,已被应用于求解数值优化问题、流水线调度问题和结构工程优化问题[8-13]。为了能够应用HSA求解具有二进制编码的组合最优化问题,本文提出了一种二进制和声搜索算法(Binary Harmony Search Algorithm,BHSA),并利用BHSA分别求解著名的k.可满足性问题(k.SATisfiability,k.SAT)和0.1背包问题(0.1KP),通过对大规模k.SAT实例和0.1KP实例的计算对比表明:BHSA是一种比二进制粒子群优化(Binary BPSO, BPSO)和GA更适宜用来求解具有二进制编码组合最优化问题的新算法。 1 二进制和声搜索算法 和声搜索算法(HSA)[8]是借鉴乐师们凭借记忆通过反复调整各乐器的音调而最终达到一个美妙的和声状态的思想实现进化的。在HSA中,各乐器的和声对应于解向量Xi=(xi1,xi2,…,xin),评价结果对应于目标函数f(Xi),和声记忆库(Harmony Memory,HM)对应于种群Pop={X1,X2,…, Xm},而乐曲的创作过程即为种群的进化过程。在基本HSA中,算法首先随机产生HM,然后通过对HM的记忆思考、对音调的定调修正以及随机选择音调三种操作来产生候选解,并将候选解与HM中的最差 [1] [2] [3] [4] 下一页 |
|
|
|
上一个论文: 区域战略的“文化张力” 下一个论文: 情感是播音艺术之魂 |
|