数学建模十类经典算法(3)

百年孤独

98年全国大学生数学建模竞赛A题
1 e# j9 B/ t* \, |1 D投资的收益和风险
4 n: c- a; `" q7 c2 m/ t) b一、模型的建立
0 w  l/ \5 O- E% G设购买Si的金额为Xi，所需的交易费ci (xi)为：
3 v5 r8 D% R! l) i' ~4 g% H

设存银行的金额为x0,显然c0(x0)=0
  @# o/ D+ V4 S6 E: Q. Y对si投资的净收益为Ri(xi)=rixi-ci(xi)
+ N# W5 o( ?: C* h* t0 ]投资组合x=(x0,x1,…xn)的净收益为
  l5 f8 u2 ^$ ^1 B' ^3 ]
由题意，投资的风险为Q(x)=max(qixi)
因此，问题的数学模型是一个双目标优化：
. _+ U3 \$ x3 T" Hminz1=Q(x)
+ n; W5 m7 N1 \+ ]  sminz2=-R(x)
s.t
4 J) z: L9 E2 }; M
二、模型求解

. V- i/ s: \+ i) H5 y0 a/ p# ?8 x* z  s对于上述双目标优化模型这类问题大多用某种方式化为单目标问题来求解，主要有以下三种：（1）固定风险水平，优化收益；（2）固定赢利水平，极小化风险；（3）确定投资者对风方法险—收益的相对偏好系数。前（1）、（2）两种方法分别是以牺牲某一目标来达到另一目标的优化，而对第三种则由于决策者很难知道偏好系数具体的值。故这三种方法都不太理想， 下面我们考虑用遗传算法来解决这个问题。
由于在双目标情况下，两目标通常本质上是相互矛盾的，最优解需要替代为非劣解，即对于任何目标函数在不牺牲其它目标的情况下就不能改进的解。
7 j& ^4 O$ v# [2 w! z9 c三个定义
定义1：非劣解：可行解
5 T, k2 q3 H0 e0 N定义2：正理想解：正理想解由所有可达到的最好的目标值构成
* _" [7 w9 Y" C- c: ^, z9 {# y定义3：负理想解：负理想解由所有可达到的最坏的目标值构成
我们考虑用遗传算法产生整个非劣解的集（和谐）合，或近似的集（和谐）合，然后让决策者自己来选择最好地表达他对各个目标的权衡取舍的非劣解。对于这个双目标规划问题可采用自适应移动线技术建立一种求加权和的方法，这种方法可迫使遗传搜索去探索目标空间中非劣解的集（和谐）合。
9 c* a* q: v2 F9 a* a8 [2 \/ q3 e& [  f
总的步骤：
% h& T! d: B$ [+ V+ ^4 t* L! K5 c步骤1：构造染色体，产生初始种群：选用二进制编码，随机产生一组染色体xk放入**E中
步骤2：染色体交叉，对上面产生的种群按交叉概率pc
选择“个体对”进行单点交叉。一般取pc从0.25到1.00之间。
: A" n, h- s6 @& i5 ^2 X8 W& Z步骤3： 染色体变异：为使群体保持多样性，可按变异率pm进行变异（可随机选择变异点）
步骤4：
, @7 n/ c  o+ f) a3 A: h  P+ q更新**E：1）对双亲和后代的每个染色体计算两个目标的值；
6 g1 P, h6 f) }（2）将新的非劣解加入E，从而更新E并从E删去劣点；
（3）确定**E 中新的特殊点
步骤5：评估：按公式计算双亲和后代的每个染色体的适值。

步骤6 ：
. V* D1 e/ [9 u/ t; K选择：
（1）删去所有重复的染色体；
（2）按降序排列余下的染色体；
6 y4 U# U2 ?4 ]（3）选择前pop_size 个染色体组成新的种群.
步骤7: 检查终止条件：若运行次数已达预先确定的代数目则停止，否则转步骤2
+ E& n+ _1 O! y6 ?' f' C) D故运用该算法若干次后最终能得到一个非劣解集，供决策者参考.
遗传算法从多个初始点开始寻优，沿多路径搜索，可获全局或准全局最优解. 我们可类似地用上述算法获得多目标规划模型的非劣解**.