熊小华, 马 良, 宁爱兵

(1.上海理工大学管理学院,上海 200093;2.上海第二工业大学计算机与信息学院,上海 201209)

多目标0-1规划的元胞竞争决策算法

熊小华1,2, 马 良1, 宁爱兵1

(1.上海理工大学管理学院,上海 200093;2.上海第二工业大学计算机与信息学院,上海 201209)

将元胞演化规则与竞争决策算法相结合,提出了一种求解多目标0-1规划问题的元胞竞争决策算法.大量数据测试和验证表明,该算法能有效提高非劣解的分布性和多样性.

竞争决策算法;元胞自动机;多目标;0-1规划

多目标0-1规划是以一维背包问题的0-1整数规划为原型发展起来的多个约束、多个目标的最优化问题,在投资决策、经济预算以及资源分配等问题中有着广泛的应用.这种具有多个约束、多个目标的组合优化问题,统称为多目标优化问题(MOP)[1-2].针对多个彼此冲突的目标,如何获取这些问题的最优解,一直都是科学界和工程界关注的焦点问题.由于多目标意义下,使得所有目标都达到最佳的最优解往往并不存在,一般所要求的都是一组相互之间无法区分优劣的非劣解(non-dominated solution),也称有效解或Pareto解.多目标优化问题的Pareto解只是一个可以接受的非劣解,并且大多数的Pareto解的个数很多,甚至是无穷大[2].

0-1整数规划属于NP(非确定多项式)完备问题类,是否存在有效算法尚不可知,已有的精确算法仅能解决小规模问题,而启发式算法又不能保证得到的解是最优的.多目标0-1规划问题相比单目标0-1规划来说,更增加了问题求解的难度.对于多目标的组合优化问题,国内外的有关研究较少,尤其缺乏实用算法.本文将对此作一些探索性的研究,为这类离散型的多目标优化难题提供若干解决手段,对这些模型的实际应用奠定方法和技术上的基础.本文将竞争决策算法原理与元胞自动机的演化规则相结合来求解多目标0-1规划问题,更好地发挥竞争决策算法的优势,既能达到Pareto前沿,又能提高解的分布性和多样性.

1 竞争决策算法简介

竞争决策算法(competitive decision algorithm,简称CDA)是近几年来提出的一种求解组合优化难题的新型算法[3-8],算法的原理详见文献[5].自然界中的竞争和决策都是在一定竞争规则下,在竞争者的实力、竞争者和环境间的关系、多个竞争者实力的差距和初始竞争状态等多种因素的共同作用下,经过多次竞争和决策后,使不同的竞争者分别占有一定的资源而达到一种新的竞争状态,只要新的竞争状态优于初始竞争状态,就能达到优化的目的. CDA算法吸收了达尔文“优胜劣汰”的进化思想以及演化博弈论中有限理性竞争者的思想,通过构造一个或多个具有有限理性的竞争者参与到对一个或多个资源的竞争过程中,通过优胜劣汰的原则使一部分竞争者获得资源而增加实力,一部分竞争者失去资源削弱实力甚至消亡.当算法通过竞争不能获得更优的结果时,通过资源交换使算法进入下一轮的竞争.在理论方面,现在已给出了竞争决策算法的基本概念和通用流程;在应用方面,已利用其通用流程给出了车辆路径问题、度约束最小生成树、旅行商问题等NP难题的算法并编程实现.

2 元胞自动机简介

元胞自动机(cellular automata,简称CA)最早由冯·诺依曼提出,沃尔夫勒姆等[9-10]将动力系统方法、计算理论及形式化语言方法引入元胞自动机的研究中,促进其广泛应用.CA是一个时间和空间都离散的动力学系统,由元胞、状态、邻居和规则这4部分组成.按一定拓扑结构分布的元胞仅取有限的离散状态,依据确定的局部规则进行更新,大量元胞通过简单的相互作用而构成动态系统的演化.若元胞的状态数为k,邻居数为n,则元胞的可能状态数为kkn.元胞在邻域范围内具有多种变化形态,这增加了种群的范围,提高了解的搜索空间,可以避免算法陷入局部最优的状况,这也是将元胞自动机引入竞争决策算法的原因所在.

3 多目标0-1规划的元胞竞争决策算法

3.1 问题介绍

本文考虑如下形式的多目标0-1规划问题

式中,zi为第i个目标的值;m为约束的个数;n为决策变量的个数;k为目标的个数.

3.2 算法原理

具有n个决策变量、m个约束条件以及k个目标的多目标0-1规划问题,将n个决策变量看成竞争者争夺的资源,将k个目标看成非虚拟竞争者A,另一个竞争者是虚拟竞争者N.竞争开始时所有的资源为N所占有,A不占有任何资源.在竞争过程中,A按照竞争力函数和决策规则占有决策变量资源,在竞争的过程中要保证满足所有的m个约束.竞争结束后A占有的决策变量即是值为1的决策变量.

3.3 基本符号及含义

为了方便描述,现介绍本文采用的符号.

3.4 竞争力函数、决策函数和资源交换规则

3.4.1 竞争力函数

本算法采用6个竞争力函数,现描述所采用的竞争力函数的基本思想.在满足m个约束条件的前提下:a.sum_profit(j)值越大的决策变量竞争力函数越大;b.min_profit(j)值越大的决策变量竞争力函数越大;c.-diff_profit(j)值越大的决策变量竞争力函数越大;d.sum_dentisity(j)值越大的决策变量竞争力函数越大;e.min_dentisity(j)值越大的决策变量竞争力函数越大;f.-diff_dentisity(j)值越大的决策变量竞争力函数越大.限于篇幅,仅给出1个竞争力函数的定义,其他5个竞争力函数定义类似.

3.4.2 决策函数

本文只采用1个决策函数,即选中竞争力函数power(j)值最大的决策变量.若两个决策变量的power(j)值相同时,则选择编号小的决策变量.

3.4.3 资源交换规则

在元胞空间里,元胞按照演化规则有很多种变化,有助于保持种群的多样性.在多目标问题求解中,为了提高Pareto解集的多样性和分布性,将元胞自动机的演化规则用作竞争决策算法的资源交换规则,以使竞争进入下一个竞争均衡状态.

定义1 集合X=(x1,x2,…,xn),xi∊{0, 1}.X中xi的任意取值的组合构成的集合为元胞空间,则元胞空间可以定义为L={CellX=(x1,x2,…,xn)｜xi∊{0,1}},CellX表示一个元胞.

定义2 元胞邻居采用扩展Moore邻居类型, N={CellY｜diff(CellY-CellX)≤r,CellX,CellY∊L},其中,diff(CellY-Cell X)为两个组合的差异.若无差异,为0;有差异时,最大为2.r表示差异的程度,本文中r取2.

定义3 Pareto解集过滤器,用来存放运行时产生的Pareto解.对于不违反约束的解,若该解支配过滤器中某个解,则将该解加入过滤器,同时删除受支配解;若过滤器中某个解支配该解,则放弃该解.过滤器的大小可以事先设定好,过滤器的大小限制了允许保存的最多的Pareto解的个数.

定义4 元胞演化规则:将已经求得的解看成中心元胞CellX.按照元胞邻居的定义,计算其邻居CellY(CellY∊N)的各个目标值.将CellY的各目标值通过Pareto解集过滤器进行检测.

3.5 算法流程

现给出多目标0-1规划的元胞竞争决策算法流程.

Step 2.2 本轮竞争阶段2:资源交换阶段.

以本轮求得的解为中心元胞,按照元胞邻居及演化规则的定义,在邻居范围内演化,替换当前非劣解或添加新的非劣解.

Step 3 输出竞争得到的结果.

3.6 时间复杂度分析

在Step 1中分别对sum_profit(j),min_profit(j), diff_profit(j),sum_dentisity(j),min_dentisity(j)和diff_dentisity(j)采用折半插入排序进行降序排序,折半插入排序的时间复杂度为O(n log);Step 2.1最坏情况下时间复杂度为O(nm);Step 2.2中寻找元胞邻居的时间复杂度为O(n2),对每个邻居与保存的最优解的比较次数为O(k*Pareto过滤器大小),则Step 2最坏情况下的时间复杂度为O(Pareto过滤器大小*k*n2).由此可知整个算法的复杂度为O (Pareto过滤器大小*k*n2).

4 数值算例

为验证算法的有效性,采用Delphi 7.0在PC机上实现了该算法.本算法对大量的算例进行求解,并与其他算法的结果进行比较,总体效果良好,限于篇幅,现给出其中的4个算例的比较结果.

算例1 算例1取自文献[11-12].

本算法与其他算法运行的结果如表1所示,从实验结果可以看出,元胞竞争决策算法所求Pareto解的个数多于One-stage算法和DEA算法.

表1 算例1的计算结果Tab.1 Results of example 1

算例2 算例2取自文献[13-14].

本算法与其他算法运行的结果如表2所示,从结果可以看出元胞竞争决策算法相比于元胞蚁群算法、蚁群算法和遗传算法,可以找到更多的Pareto解.

表2 算例2的计算结果Tab.2 Results of example 2

算例3 算例3取自文献[14-15].

本算法与其他算法运行的结果如表3所示,相比于文献[14-15]的算法,可以发现更多的Pareto解.

算例4 k=2,n=100,m=2,其约束和目标函数由于决策变量个数较多不便列出,共求得160个Pareto解,其所求解集如图1所示.

表3 算例3的计算结果Tab.3 Results of example 3

图1 算例4的Pareto解集Fig.1 Pareto set of example 4

通过以上测试发现,对于较小规模的问题,可以求出全部Pareto解;对于较大规模的问题,Pareto解分布比较稠密,且形成一个明显的Pareto前沿.

5 结束语

多目标0-1规划问题是很多问题的原始模型,在工程实践与科学研究中都具有非常重要的意义.但是,由于其NP难题以及多目标问题本质上多个目标相互冲突的特性,限制了精确算法对较大规模问题的求解.竞争决策算法是一种能广泛应用于求解各类组合优化难题的新型寻优算法,其通用性和实用性都比较强.本文将元胞自动机原理与竞争决策算法相结合来求解多目标0-1规划问题,提高了Pareto解集的分布性及多样性,因此,求解的速度与效果都比较好.

[1] 雷德明,严新平.多目标智能优化算法[M].北京:科技技术出版社,2009.

[2] 崔逊学.多目标进化算法及其应用[M].北京:国防工业出版社,2006.

[3] 宁爱兵,马良.竞争决策算法及其在车辆路径问题中的应用[J].管理科学学报,2005,8(6):10-18.

[4] 宁爱兵,马良.度约束最小生成树(DCMST)的竞争决策算法[J].系统工程学报,2005,20(6):630-634.

[5] 宁爱兵,马良,熊小华.竞争决策算法原理及其应用[J].上海理工大学学报,2008,30(4):369-373.

[6] 熊小华,郭文夷,宁爱兵.具有偏好选择的多目标TSP竞争决策算法[J].上海第二工业大学学报,2005,22 (1):6-12.

[7] 宁爱兵,马良.最小比率旅行商(MRTSP)问题竞争决策算法[J].计算机工程与应用,2005,41(11): 30-32.

[8] 宁爱兵,马良.基于快速下界估算的瓶颈旅行商问题竞争决策算法[J].上海理工大学学报,2005,27(3): 223-228.

[9] WOLFRAN S.Theory and Application of Cellular Automata[M].Singapore:The World Scientific Publishing Company Limitd,1986.

[10] 朱刚,马良.函数优化的元胞蚂蚁算法[J].系统工程学报,2007,22(3):305-308.

[11] LIU Fuh-hwa Franklin,HUANG Chueng-chiu,YEN Yu-lee.Using DEA to obtainefficient solutions for multi-objetive 0-1 linear programs[J].European Journal of Operational Research,2000,126(1):51-68.

[12] JAHANSHAHLOO G R,HOSSEINZADEH F,SHOJA N, et al.A method for generatingall efficient solutions of 0-1 multi-objective linear programmingproblem[J]. Applied Mathematics and Computation,2005,169(2): 874-886.

[13] 崔雪丽,马良.多目标0-1规划的蚂蚁算法[J].计算机应用与软件,2007,24(7):23-24.

[14] 刘勇,马良,许燕秋.多目标0-1规划问题的元胞蚁群优化算法[J].系统工程,2009,27(2):119-122.

[15] 冯爱芬,杨森.一类农业生产问题的多目标规划模型及其解法[J].黄冈师范学院学报,2004,24(3): 32-34.

Cellular competitive decision algorithm for multi-objective 0-1 programming problem

XIONGXiao-hua1,2, MA Liang1, NINGAi-bing1
(1.Business School,University of Shanghai for Science and Technology,Shanghai 200093,China;
2.College of Computer and Information,Shanghai Second Polytechnic University,Shanghai 201209,China)

Combining the concepts of cellular automata with competitive decision algorithm,a cellular competitive decision algorithmfor multi-objectives 0-1 programming problem was presented.The algorithm was then used to solve many instances of multi-objectives 0-1 programming and the computational results show it can improve effectively the diversity and distribution of Pareto optimal set.

competitive decision algorithm;cellular automata;multi-objectives;0-1 programming

O 223

A

1007-6735(2011)02-0163-05

2011-02-25

国家自然科学基金资助项目(70871081);上海市重点学科建设资助项目(S30504).

熊小华(1978—),女,博士研究生.研究方向:算法设计、系统工程.E-mail:xiong_xiao_hua@163.com;

马 良(联系人),男,教授.研究方向:算法设计、系统工程.E-mail:maliang@usst.edu.cn