利用遗传算法求解最佳分配问题.pdf-资料库

中国科技论文在线 http://www.paper.edu.cn 利用遗传算法求解最佳分配问题周秀丽，孙桐，李洋辽宁工程技术大学理学院，辽宁阜新（123000） Email：zxl5021@126.com 摘要：本文应用遗传算法解决了最佳分配问题，并提出了该算法在处理这一问题中的一些方法，定义了交换算子和突变算子，建立了科学、合理、有效的新模型，而且便于编程，解决了传统决策方案模型的人工性。关键词：遗传算法；最佳分配；随机矩阵中图分类号：O221 1 引言管理手段的现代化是现代化管理的必要条件之一。从管理现代化和企业效益最优化的需求出发，要确保企业、部门、区域的经济管理状况最优或要保证某项投资方案及发展规划的预期效果最佳，就必须从全局角度考虑整体效用最优化问题，这里以投资决策方案为例。 2 问题分析 , 集 Z = , 2 z 2 , L mx } z ,{ 1 ，决策目标集 X xx ,{ = 设决策对象集，影响目标的因素 1 ； ijs 表示对象 ix 具有程度 jz 的水平值， pqt 表示因素 pz 对目标 qy 的 wz , } i wmijs ,2,1 { ; = 影响程度水平值， TSC 便是决策所依据的对象与目标间的模糊关系矩 pjm , L ( =×= ；模糊关系矩阵 yy ,{ 1 ,2,1 = nmijc ) 的乘积 qw ; ,2,1 n }, ny } L L L = ( L , 2 Y = ) × S , , = , = T pqt ) ( 和阵[1]，其中 nw × × c ij w = ∑ k 1 = ts ik kj i ( = ,2,1 L , jm ; = ,2,1 n ), L . （2-1）传统的最佳分配决策方案模型如下：（1）确定模糊关系矩阵 S 和 T，并计算矩阵 C （2）矩阵消元过程求l ,(l 为寻求一般分配问题的优化水平)。（3）用l平铣关系矩阵 C 后得 0C ——作为最佳决策方案的决策依据，对 0C 采用“寻踪” 过程便可求出最佳决策方案。其中 0C 的计算公式为 c 0 ij = c ⎧ ⎪ ij ⎨ 0 ⎪⎩ c ij c ij ≥ < l l . （2-2）但第二步和第三步的“寻踪”过程都比较复杂，尤其“寻踪”过程比较人工化，对于有较多决策对象和决策目标时，处理起来相当困难。针对该种情况本文给出了一种新的决策方案——遗传算法，则此问题的数学模型可表示为： max Wf ( ) = 6 14 ∑∑ i 1 − j 1 = ijwc ji （2-3） s.t. 14 =∑ w ji i 1 = 1 j ,2,1 L= 6, （2-4） -1-

http://www.paper.edu.cn i ,2,1 L= 14, （2-5） j = ,2,1 ;6 L = i ,2,1 （2-6） 14, L 1=jiw 中国科技论文在线 1 6 ji w ≤∑ j 1 = w ji 1,0 = 其中，若 0=jiw ，则表示第 i 个城市没能投资第 j 个项目；相反，若，则表示第 i 个城市能投资第 j 个项目。 3 遗传算法 3.1 遗传算法的基本原理遗传算法起源于对于生物系统所进行的计算机模拟研究，最早由 Holland 教授受到生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的实惠鱼复杂系统优化的自适应概率优化算法——遗传算法[2]。遗传算法是模拟自然界生物进化机制发展起来的随机全局搜索和优化方法，其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得全局最优解。 3.2 遗传算法的实施过程[3] （1）对研究的变量或对象进行编码（形成字符串）并随机地建立一个初始群体。（2）计算群体中诸个体的适应度。（3）执行产生新群体的操作，包括： a. 复制。将适应度高的个体进行复制后添加到新群体中，删除适应度低的个体； b. 交换。随机选出个体对，进行片段交差换位，产生新个体对； c. 突变。随机地改变某个体的某个字符，而得到新个体。（4）根据某种条件判断计算过程是否可以结束，如果不满足结束条件，则返回到步骤（2），直到满足结束条件为止。 4 遗传算法在最佳分配问题中的应用 4.1 最佳分配问题城市，将分别实施 6 个投资项目现在考虑一项投资计划，该计划要在国务院首批公布的 14 个沿海开放城市中选择 6 个 } 。而针对这 6 个项目可能取定影响目标的因素集为 Z={地区水利水电供应，土地使用管理，地理及通信交通，劳动力资源，周边地区自然资源}，其中 X 中依次表示 Z 元素是 14 个城市的随意排列，与公布顺序无关；为方便计，用和 6y 。这里对象集 yy ,{ 1 xx ,{ 1 yy , 1 目标集 x 14 L L X Y = = } y y y , y , , , , , , 5 z 1 , z 2 , z 3 , z 4 , z 5 2 2 3 4 ， 2 6 中各元素。模糊关系矩阵 S = ( wmijs ) × 可由统计资料获取（用简单统计加权、界点法、多元逻辑排他发等多种可能的方法）； TSC 可求得，结果如下： =×= nmijc ) ( × T = pqt ( ) nw × 可依据实际情况事先设定。则 -2-

中国科技论文在线 http://www.paper.edu.cn C = 86.0 56.0 63.0 70.0 72.0 78.0 65.0 65.0 74.0 80.0 71.0 80.0 70.0 72.0 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 77.0 74.0 72.0 41.0 73.0 79.0 65.0 69.0 85.0 85.0 71.0 70.0 72.0 70.0 76.0 79.0 74.0 73.0 72.0 78.0 72.0 72.0 86.0 88.0 72.0 74.0 74.0 76.0 50.0 70.0 74.0 71.0 77.0 78.0 58.0 64.0 87.0 84.0 70.0 71.0 72.0 67.0 73.0 71.0 66.0 59.0 78.0 82.0 55.0 50.0 56.0 61.0 73.0 72.0 63.0 72.0 58.0 71.0 70.0 66.0 77.0 79.0 59.0 59.0 73.0 83.0 73.0 72.0 69.0 72.0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ 4.2 对可行解进行编码，建立一个初始群体一个最佳分配方案可用一个分配矩阵描述：（2-6）的W 被称为一个染色体。 nmijwW = ) ( × ，满足条件（2-4）、（2-5）和在初始群体的选取时应该构造一个程序，使得产生的所有个体满足条件（2-4）、（2-5）和（2-6）。 4.3 适应度的规定取目标函数 Wf ( ) = 作为评价染色体W 的适应度函数。 4.4 执行产生新群体的操作 4.4.1 复制 14 ∑∑ 6 i 1 − j 1 = ijwc ji （4-1）复制是遗传算法的基本算子，对当前群体实施复制操作可以使适应度高的优良个体尽可能地在下一代新群体中得以繁殖，体现“适者生存”的自然选择原则，同时还使新一代群体中的个体数量与原来群体的相同。在遗传算法中，并不是简单的利用适应度的大小来选择复制对象，为了保证适应度高的个体被抽到的机会大于适应度低的个体，可以选择轮盘选择法[4]。 4.4.2 交换 -3-

中国科技论文在线 http://www.paper.edu.cn 0 0 0 0 0 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ 和 00 00 0 0 0 0 0 0 00 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 10 0 0 0 00 00 0 0 0 00 0 0 00 0 00 0 0 100 0 0 00 00 0 0 00 0 00 010 0 0 0 0 0 000 0 ⎞ ⎟ 0 ⎟ ⎟ 0 ⎟ 0 ⎟ ⎟ 0 ⎟ ⎟ 0 ⎠ 被选作交换运算的父代，交换 0 = 1W 设矩阵 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 01 0 0 0000 1 0100 0 000 0 0 00 0 0 0 00 0 00 0 10 00 0 00 0 0 0 0 0 0 0 0 0 0 0 1 010 0 0 0 000 0 0 0 运算由以下三步来实现：（1）建立两个临时矩阵 00 0 100 00 0 000 00 00 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 2W = r ij = ,0 ⎧ ⎪ ⎨ ,1 ⎪⎩ [ ijdD = d ] 和 =< ij ] ，其中 x 2/) )2( ij w )2( ij R = [ ijr x ( )1( + ij w )1( 若 ij 否则 + > （4-2）能被 2 整除（4-3） = D 0 0 0 1 0 0 0 0 0 0 0 0 0 0 00 00 0 0 0 0 0 0 0 0 公式（4-2）中< y >表示对实数 y 保留整数部分。按式（4-2）及（4-3），得到两个临时矩阵： 0 00 0 0 0 00 ⎛ ⎜ 000 00 0 0 0 ⎜ ⎜ 0 00 00 0 0 0 ⎜ 0 00 000 0 0 ⎜ ⎜ 00 0 00 00 0 ⎜ ⎜ 000 00 000 ⎝ 00 0 0 01 0 ⎛ ⎜ 100 0 00 0 ⎜ ⎜ 0100 010 00 ⎜ 0 00 0 0000 ⎜ ⎜ 0 010 1000 ⎜ ⎜ 0 100 00000 ⎝ 不难看出，矩阵 1W ， 2W ， D 和 R 之间满足关系 0010 0010 0 0 0 0 0 0 00 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ⎞ ⎟ 0 0 ⎟ ⎟ 0 0 ⎟ 0 0 ⎟ ⎟ 0 0 ⎟ ⎟ 10 ⎠ 0 0 0 R = ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ 1W + 2W =2 D + R （4-4）同时，还有一个有趣的性质是 R 的各行若含有 1 元素，则有且仅有两个，否则只为 0 元素. （2）把矩阵 R 拆成两个矩阵 1R 和 2R ，拆分的方法是让 1R 和 2R 中的每列和每行各保留一个 1（如果有 1 的话）。显然这样的拆分方法会有好多种，但有两个要求，即 1R 不能等于 1W - D -4-

中国科技论文在线 http://www.paper.edu.cn 或 2W - D （ 2R 也不能等于 1W - D 或 2W - D ），且 1R 和 2R 必须满足条件（2-5），所以在前面的例子中，对 R 的一种拆分是 1R 2R = 0 0 00 00 0010 0 00 ⎛ ⎜ 100 0 00 0 ⎜ ⎜ 0000 0 0 0 ⎜ 0000 00 0 ⎜ ⎜ 000 0 00 0 ⎜ ⎜ 00000 0 0 ⎝ 0 00 01 ⎛ ⎜ 0010000 ⎜ ⎜ 0100 0 ⎜ 0000 0 ⎜ ⎜ 1000 0 ⎜ ⎜ 00000 0 ⎝ 因为 1R + 2R = R ，代入式（4-4），有 0 0 0 0 010 00 0 0 00 0 0 010 0 0 00 0 0 0 00 0 0 0 0 00 0 0 00 00 0 0 00 0 0 0 00 0 0 0 100 0 0 00 00 0 0 0 = 0 0 ⎞ ⎟ 0 0 ⎟ ⎟ 0 0 ⎟ 0 0 ⎟ ⎟ 0 0 ⎟ ⎟ 10 ⎠ 0 0 ⎞ ⎟ 0 0 ⎟ ⎟ 0 0 ⎟ 0 0 ⎟ ⎟ 0 0 ⎟ ⎟ 0 0 ⎠ 1R + 2R =（ D + 1R ）+（ D + 2R ）（4-5） 1W + 2W =2 D + 于是，可以得到 1W 和 2W 的两个子代。 1W 和 ’ （3）取 1W 和 2W 的两个子代 ‘ 1W = D + 1R ， ’ 2W 分别为 ‘ 2W = D + 2R 继续前面的例题，得到 ‘ = 0 0 00 00 1W = D + 1R 0010 0 00 100 00 0 0 0000 0 0 0 0000 00 10 000 0 00 0 0 00000 0 0 0 0 0 0 0 00 01 000 0 00 0 1 0100 0 0 0 0 0000 0 0 10 1000 00 0 0 00000 0 0 0 0 0 0 0 0 00 00 0 0 0 0 这样操作所得到的子代个体都是可行的（满足约束条件的）。 0 0 0 0 ⎞ ⎟ 0 0 0 0 ⎟ ⎟ 0 0 010 00 ⎟ 0 0 00 0 ⎟ ⎟ 0 0 010 ⎟ ⎟ 00 0 10 ⎠ 00 0 0 0 ⎞ ⎟ 00 0 0 0 ⎟ ⎟ 00 0 0 ⎟ 00 0 0 ⎟ ⎟ 00 0 0 ⎟ ⎟ 010 0 ⎠ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 2W = D + 2R = ’ 4.4.3 突变因为染色体W 是 6 行 14 列矩阵。生成两个随机整数 ( ，交换W 选定的第 ))14,1( 行或第 , 1, pp 2 ∈qqqq 1 , 2 1 2 1,qq 2 p ， 1 ∈ppp 2 ( , 2 1 ))6,1( （或列的元素。例如，突变个体为 -5-

中国科技论文在线 http://www.paper.edu.cn 1W ，产生的两个随机数为 2 和 4（针对行），则突变后新个体为 ‘W 1 = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 0 0 01 0000 0100 000 00 0 00 0 0 0 0 10 0 0 00 00 00 0 0 0 0 0 0 00 0 0 01 0 0 0 0 0 0 0 10 0 00 00 0 0 00 0 00 010 0 0 0 0 0 000 0 0 0 0 0 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ，显然突变后的个体仍为满足条件的个体。 4.4.4 运算终止根据某种条件判断计算过程是否可以结束，如果不满足结束条件，则继续进行迭代计算，直到满足结束条件为止。在本问题中可以依据人的经验或对问题的期望提出一个理想的适应度值（即能度），一旦某代最优个体的适应度超过了这个理想值，则迭代运算停止。 5 结论遗传算法是模仿生物遗传与进化过程而得出的一种随机优化方法，对非线性、多极值的寻优是一种有效方法。本文对可行解进行了编码，表示成“染色体”，并有随机方法产生的一群“染色体”组成初始种群，通过适应度构成优胜劣汰、适者生存的“自然环境”，定义了新的遗传算子，使种群通过遗传、交换、突变等不断演化，产生出新的更加优良的种群。这样经过若干代的进化，最终求得适合问题的最优解，得到最佳决策方案，即投资方案。参考文献 [1]赵晓东，赵静一.模糊思维与广义设计.北京：机械工业出版社，1998.10 [2]郭嗣琮，陈刚. 信息科学中的软计算方法. 东北大学出版社. 2001.11 [3]雷英杰. MATLAB 遗传算法工具箱及应用. 西安电子科技出版社，2005 [4]周明，孙树栋.遗传算法原理及应用.北京：国防工业出版社，1999 Optimal distribution of the use of genetic algorithm to solve the problem Faculty of Science, Liaoning Technical University, Fuxin, Liaoning (123000) ZHOU Xiuli, SUN Tong, LI Yang Abstract In this paper, genetic algorithm to solve the optimal allocation problem, and proposed the algorithm in dealing with this issue in some ways, define the exchange operator and mutation operator to establish a scientific, rational and effective new model, and the ease of programming to solve the traditional decision-making model of the artificial nature of the program. Keywords: Genetic algorithms; optimal distribution; stochastic matrix -6-

资料库

利用遗传算法求解最佳分配问题.pdf

相关推荐

开发技术

热门标签

最新资料