【原创】非线性整数规划的遗传算法Matlab程序（附图）

aiwa

GreenSim团队的博客开通了，更多原创程序请访问我们的博客
http://blog.sina.com.cn/greensim

    通常，非线性整数规划是一个具有指数复杂度的NP问题，如果约束较为复杂，Matlab优化工具箱和一些优化软件比如lingo等，常常无法应用，即使能应用也不能给出一个较为令人满意的解。这时就需要针对问题设计专门的优化算法。下面举一个遗传算法应用于非线性整数规划的编程实例，供大家参考！

    模型的形式和适应度函数定义见后面

    这是一个具有200个01决策变量的多目标非线性整数规划，编写优化的目标函数如下，其中将多目标转化为单目标采用简单的加权处理。

1. function Fitness=FITNESS(x,FARM,e,q,w)
   
2. %% 适应度函数
   
3. % 输入参数列表
   
4. % x 决策变量构成的4×50的0-1矩阵
   
5. % FARM 细胞结构存储的当前种群，它包含了个体x
   
6. % e 4×50的系数矩阵
   
7. % q 4×50的系数矩阵
   
8. % w 1×50的系数矩阵
   
9. %%
   
10. gamma=0.98;
    
11. N=length(FARM);%种群规模
    
12. F1=zeros(1,N);
    
13. F2=zeros(1,N);
    
14. for i=1:N
    
15. xx=FARM{i};
    
16. ppp=(1-xx)+(1-q).*xx;
    
17. F1(i)=sum(w.*prod(ppp));
    
18. F2(i)=sum(sum(e.*xx));
    
19. end
    
20. ppp=(1-x)+(1-q).*x;
    
21. f1=sum(w.*prod(ppp));
    
22. f2=sum(sum(e.*x));
    
23. Fitness=gamma*sum(min([sign(f1-F1);zeros(1,N)]))+(1-gamma)*sum(min([sign(f2-F2);zeros(1,N)]));
    
24. 
    
25.     针对问题设计的遗传算法如下，其中对模型约束的处理是重点考虑的地方
    
26. function [Xp,LC1,LC2,LC3,LC4]=MYGA(M,N,Pm)
    
27. %% 求解01整数规划的遗传算法
    
28. %% 输入参数列表
    
29. % M 遗传进化迭代次数
    
30. % N 种群规模
    
31. % Pm 变异概率
    
32. %% 输出参数列表
    
33. % Xp 最优个体
    
34. % LC1 子目标1的收敛曲线
    
35. % LC2 子目标2的收敛曲线
    
36. % LC3 平均适应度函数的收敛曲线
    
37. % LC4 最优适应度函数的收敛曲线
    
38. %% 参考调用格式[Xp,LC1,LC2,LC3,LC4]=MYGA(50,40,0.3)
    
39. 
    
40. %% 第一步：载入数据和变量初始化
    
41. load eqw;%载入三个系数矩阵e,q,w
    
42. %输出变量初始化
    
43. Xp=zeros(4,50);
    
44. LC1=zeros(1,M);
    
45. LC2=zeros(1,M);
    
46. LC3=zeros(1,M);
    
47. LC4=zeros(1,M);
    
48. Best=inf;
    
49. 
    
50. %% 第二步：随机产生初始种群
    
51. farm=cell(1,N);%用于存储种群的细胞结构
    
52. k=0;
    
53. while k %以下是一个合法个体的产生过程
    
54. x=zeros(4,50);%x每一列的1的个数随机决定
    
55. for i=1:50
    
56. R=rand;
    
57. Col=zeros(4,1);
    
58. if R<0.7
    
59. RP=randperm(4);%1的位置也是随机的
    
60. Col(RP(1))=1;
    
61. elseif R>0.9
    
62. RP=randperm(4);
    
63. Col(RP(1:2))=1;
    
64. else
    
65. RP=randperm(4);
    
66. Col(RP(1:3))=1;
    
67. end
    
68. x(:,i)=Col;
    
69. end
    
70. %下面是检查行和是否满足约束的过程，对于不满足约束的予以抛弃
    
71. Temp1=sum(x,2);
    
72. Temp2=find(Temp1>20);
    
73. if length(Temp2)==0
    
74. k=k+1;
    
75. farm{k}=x;
    
76. end
    
77. end
    
78. 
    
79. %% 以下是进化迭代过程
    
80. counter=0;%设置迭代计数器
    
81. while counter
    
82. 
    
83. %% 第三步：交叉
    
84. %交叉采用双亲双子单点交叉
    
85. newfarm=cell(1,2*N);%用于存储子代的细胞结构
    
86. Ser=randperm(N);%两两随机配对的配对表
    
87. A=farm{Ser(1)};%取出父代A
    
88. B=farm{Ser(2)};%取出父代B
    
89. P0=unidrnd(49);%随机选择交叉点
    
90. a=[A(:,1:P0),B(:,(P0+1):end)];%产生子代a
    
91. b=[B(:,1:P0),A(:,(P0+1):end)];%产生子代b
    
92. newfarm{2*N-1}=a;%加入子代种群
    
93. newfarm{2*N}=b;
    
94. %以下循环是重复上述过程
    
95. for i=1:(N-1)
    
96. A=farm{Ser(i)};
    
97. B=farm{Ser(i+1)};
    
98. P0=unidrnd(49);
    
99. a=[A(:,1:P0),B(:,(P0+1):end)];
    
100. b=[B(:,1:P0),A(:,(P0+1):end)];
     
101. newfarm{2*i-1}=a;
     
102. newfarm{2*i}=b;
     
103. end
     
104. FARM=[farm,newfarm];%新旧种群合并
     
105. 
     
106. %% 第四步：选择复制
     
107. FLAG=ones(1,3*N);%标志向量，对是否满足约束进行标记
     
108. %以下过程是检测新个体是否满足约束
     
109. for i=1:(3*N)
     
110. x=FARM{i};
     
111. sum1=sum(x,1);
     
112. sum2=sum(x,2);
     
113. flag1=find(sum1==0);
     
114. flag2=find(sum1==4);
     
115. flag3=find(sum2>20);
     
116. if length(flag1)+length(flag2)+length(flag3)>0
     
117. FLAG(i)=0;%如果不满足约束，用0加以标记
     
118. end
     
119. end
     
120. NN=length(find(FLAG)==1);%满足约束的个体数目，它一定大于等于N
     
121. NEWFARM=cell(1,NN);
     
122. %以下过程是剔除不满主约束的个体
     
123. kk=0;
     
124. for i=1:(3*N)
     
125. if FLAG(i)==1
     
126. kk=kk+1;
     
127. NEWFARM{kk}=FARM{i};
     
128. end
     
129. end
     
130. %以下过程是计算并存储当前种群每个个体的适应值
     
131. SYZ=zeros(1,NN);
     
132. syz=zeros(1,N);
     
133. for i=1:NN
     
134. x=NEWFARM{i};
     
135. SYZ(i)=FITNESS2(x,NEWFARM,e,q,w);%调用适应值子函数
     
136. end
     
137. k=0;
     
138. %下面是选择复制，选择较优的N个个体复制到下一代
     
139. while k minSYZ=min(SYZ);
     
140. posSYZ=find(SYZ==minSYZ);
     
141. POS=posSYZ(1);
     
142. k=k+1;
     
143. farm{k}=NEWFARM{POS};
     
144. syz(k)=SYZ(POS);
     
145. SYZ(POS)=inf;
     
146. end
     
147. %记录和更新，更新最优个体，记录收敛曲线的数据
     
148. minsyz=min(syz);
     
149. meansyz=mean(syz);
     
150. pos=find(syz==minsyz);
     
151. LC3(counter+1)=meansyz;
     
152. if minsyz Best=minsyz;
     
153. Xp=farm{pos(1)};
     
154. end
     
155. LC4(counter+1)=Best;
     
156. ppp=(1-Xp)+(1-q).*Xp;
     
157. LC1(counter+1)=sum(w.*prod(ppp));
     
158. LC2(counter+1)=sum(sum(e.*Xp));
     
159. 
     
160. %% 第五步：变异
     
161. for i=1:N
     
162. if Pm>rand%是否变异由变异概率Pm控制
     
163. AA=farm{i};%取出一个个体
     
164. POS=unidrnd(50);%随机选择变异位
     
165. R=rand;
     
166. Col=zeros(4,1);
     
167. if R<0.7
     
168. RP=randperm(4);
     
169. Col(RP(1))=1;
     
170. elseif R>0.9
     
171. RP=randperm(4);
     
172. Col(RP(1:2))=1;
     
173. else
     
174. RP=randperm(4);
     
175. Col(RP(1:3))=1;
     
176. end
     
177. %下面是判断变异产生的新个体是否满足约束，如果不满足，此次变异无效
     
178. AA(:,POS)=Col;
     
179. Temp1=sum(AA,2);
     
180. Temp2=find(Temp1>20);
     
181. if length(Temp2)==0
     
182. farm{i}=AA;
     
183. end
     
184. end
     
185. end
     
186. 
     
187. counter=counter+1
     
188. end
     
189. 
     
190. %第七步：绘收敛曲线图
     
191. figure(1);
     
192. plot(LC1);
     
193. xlabel('迭代次数');
     
194. ylabel('子目标1的值');
     
195. title('子目标1的收敛曲线');
     
196. figure(2);
     
197. plot(LC2);
     
198. xlabel('迭代次数');
     
199. ylabel('子目标2的值');
     
200. title('子目标2的收敛曲线');
     
201. figure(3);
     
202. plot(LC3);
     
203. xlabel('迭代次数');
     
204. ylabel('适应度函数的平均值');
     
205. title('平均适应度函数的收敛曲线');
     
206. figure(4);
     
207. plot(LC4);
     
208. xlabel('迭代次数');
     
209. ylabel('适应度函数的最优值');
     
210. title('最优适应度函数的收敛曲线');

复制代码

--------------------------------------------------------------------------------

【GreenSim团队简介】

——更多原创程序，请访问GreenSim团队的主页→http://blog.sina.com.cn/greensim

    GreenSim团队长期从事建模仿真、算法设计、代写程序等业务，为您提供实验、课题、论文、项目等方面的仿真服务。
    GreenSim团队擅长的学科领域主要有
【智能算法】遗传算法、模拟退火、神经网络、蚁群算法、免疫优化、支持向量机、拟物拟人
【运筹优化】数学建模、数值优化算法、大规模/非线性问题、组合优化、NP完全问题
【信息与通信】无线通信、信号处理、计算机网络
【其它学科】任何问题，只要能归结为数学问题或者算法仿真，我们都有实力和信心解决
    GreenSim团队的联系方式：
QQ: 330264704，535115369  Email：greensim@163.com（来 信 必 复）

[ 本帖最后由 aiwa 于 2007-3-18 13:39 编辑 ]

yxzjs

while k和while counter是什么意思？如何跳出循环？

yumu_amoko

非常感谢lz分享
受教了哈:)