多目标0-1规划的萤火虫算法.pdfVIP

第43卷第9期 数学的实践与认识 Vbl．43，No．19 2013年10月 MATHEMATICSINPRACTICEANDTHEORY 0ct．．2013 多目标0·1规划的萤火虫算法 程魁，马良 (上海理工大学管理学院，上海200093) 摘要：针对于多目标。一1规划问题，给出一种新型的智能优化算法一萤火虫优化 算法对其进行求解，并在计算机上予以实现．经一系列算例测试，并与其它智能算法 进行比较，算法能获得较多的非劣解，表明算法可行有效，可求解实际应用中的相应 问题． 关键词：多目标；o．1规划；萤火虫算法 1引言 在生产、经济、科研以及工程活动等领域中，人们经常碰到这样的问题，即在进行方案、 计划、设计的时候通常需要考虑对多个目标的优化．如在选择一个工厂地址时，既要考虑到 造价、运费等经济因素，又要顾及到对环境的污染等社会因素．这其中的许多多目标问题都 可以表示为多目标。一1规划问题，如资源分配、资本预算等【1-引．多目标0一l规划问题是运 筹学中一个经典的组合优化NP难题，对于实际工程问题，特别是规模较大时，根本无法很好 地解决，所以寻找能够有效解决该问题的智能优化算法引起了很多学者的注意．经典的智能 优化算法如蚂蚁算法【3】、蜂群算法f4】等都在解决该问题上取得了相应的成果． swarm 人工萤火虫群优化算法(G10wworm nanandKN和Ghose D于2005年首先提出的一种模拟自然界中萤火虫群体智能行为的新 型仿生优化算法，该算法主要基于如下原理：萤火虫之间通过释放荧光素和环境进行通信，每 只萤火虫仅根据其周围的局部环境做．出反应，该局部环境是由每只萤火虫的动态决策范围决 定的．萤火虫群优化算法和其它群智能算法相似，不需要目标函数的梯度信息，简单易实现， 鲁棒性强．本文将在该原理的基础上，设计一种求解多目标。一1规划问题的萤火虫算法． 2数学模型 多目标。一1规划是以一维背包问题的o．1整数规划为原型，进而发展成多个目标、多个 约束，其一般的数学模型可以表示为： maXz=薹弓巧，薹弓吻，…，喜弓％ 。J∑口鹕6“=1，2，…，m 豇L1芦 【巧∈{o，1)， J=1，2，…，m 收稿日期：2013-03．06 资助项目：国家自然科学基金；上海市研究生创新基金(JwcxsLl202) 19期 程魁，等：多目标0-1规划的萤火虫算法 63 由于在多目标意义下，使得所有目标都能达到最优解通常并不存在．因此，一般要求寻找 劣解． 3萤火虫算法 捕捉极值域速度快，捕捉效率高，具有较强的通用性等优点．萤火虫群优化算法是无记忆的， 无需目标函数的全局信息和梯度信息，简单易实现，目前已应用于诸多领域．例如一些学者将 其应用于多模态函数优化【7】、多信号源探测【81、组合优化19】等领域，并取得了良好效果． 在基本的GSO算法中，每只人工萤火虫分布在目标函数的定义空间内，这些人工萤火虫 各自携带自身的萤光素，并且拥有各自的视野范围，称为区域决策范围(10cal一decisionrange)． 区域决策范围的大小会受邻居数量的影响，当邻居密度较低，萤火虫的决策半径会加大以利 于寻找更多的邻居；反之，决策半径减小．在萤火虫的运动当中，每一只萤火虫以一定的概率 向其领域范围内的邻居萤火虫前进．萤火虫j要成为萤火虫i的邻居萤火虫，必须满足歹在l 的领域范围之内并且J的荧光素要高于i．最终，通过萤火虫群的不断运动，较多的萤火虫会 聚集在适应度值较高的萤火虫周围【5】． 在GSO当中每一次迭代都由两个阶段组成，第一阶段是萤光素更新阶段，第二阶段是萤 火虫的运动阶段． 荧光素更新阶段：在此阶段中，每一只萤火虫都按如下公式来对荧光素进行更新。 ct(亡)=(1一