GENOCOP算法在0—1非线性整数规划模型中的应用

第３ｏ卷第５期　Ｖ０１．３０　Ｎｌ０．５　长春师范学院学报（自然科学版）　Ｊｏｕｍａｌ　０ｆ　ＣＡｍ￣ｈｕｎ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　２０１１年１Ｏ月　Ｏｃｔ．２０１ｌ　ＧＥＮＯＣＯＰ算法在０—１非线性整数规划模型中的应用　袁［摘晓，利洁婷，王世其　（湛江师范学院数学与计算科学学院，广东湛江５２４０４８）　要］本文针对某公司电力容量扩展问题，采用一元线性回归模型拟合未来ｌ０年的需求量，再建　立０—１非线性整数规划模型，并将该模型的０—１变量连续化处理，采用遗传算法中的ＧＥＮＯＣＯＰ算　法求解。　【关键词］线性拟合；非线性整数规划模型；ＧＥＮＯＣＯＰ算法　［中图分类号］Ｏ２２１．２　［文献标识码］Ａ　［文章编号］１００８—１７８Ｘ（２０１１）０５—００１６—０５　０—１型混合非线性整数规划是整数规划模型中使用非常广泛的一种模型，但是由于本身的复杂性，没有　统一的方法求解．常用的求解思路主要有两大类：将混合变量全部转化为离散型变量或者全部转化为连续型变　量求解．本文针对某个建立混合整数非线性规划模型的某公司电力容量扩展问题，设计将所有０—１变量连续　化处理，从而采用求解线性约束的优化问题的ＧＥＮＯＣＰＯ算法较好地解决该问题．　１问题提出　１．１问题提出与数据收集　本问题根据　呷ｅ　Ｌ．Ｗｉｎｓｔｏｎ在文献［１］提出的案例１１改编：　Ｂｒｉｔｅ　Ｐｏｗｅｒ是纽约州Ｆｉｎｇｅｒ湖区的一家小型工厂投资电力公司．为了能够扩大公司电力生产，该公司董事　会在２０１０年夏季决定进行一项研究，主要要求有：（１）确保公司到２０２０年之前有充足的电力；（２）这项研究要　求时间范围为ｌ０年；（３）这项研究关心的是一年的电力容量，而不是每天或每小时的用电波动情况．Ｂｒｉｔｅ　Ｐｏｗｅｒ　公司主要提供的数据有：　（工）到２０１０年年初，Ｂｒｉｔｅ拥有的工厂具备６０兆瓦特的电力容量．　（Ⅱ）公司在过去１Ｏ年内电力需求量如下表　表１　２００１—２０１０年公司的电力需求量统计　年份　２ｏ０１　２００２　需求量（兆瓦特）　３６　３７　年份　２０ｏ６　２Ｏ０ｒ７　需求量（兆瓦特）　４８　５３　２００Ｂ　２００４　２０Ｑ５　４０　４２　４６　２０ｏ８　２００９　２Ｏｌ０　５４　５８　６ｌ　（１ｌＩ）燃煤工厂的经济情况根据幂定律［２３运行——也就是说，新工厂的恒定美元成本（有时候也称为“第０　年的美元”）遵循预测规则：容量为Ｋ的工厂成本＝［容量Ｋ／基本规模的工厂容量］。　＊基本规模工厂的成本。　（Ⅳ）在这次分析中，假设基本工厂的生产能力是５兆瓦特；成本是１　８００万美元．建造新工厂假设很短，当　年生产当年使用．　（Ｖ）Ｂｒｉｔｅ　Ｐｏｗｅｒ可以建造５、１０、ｌ５、２０兆瓦特生产能力的工厂，每年至多能建造一个工厂．　［收稿日期］２０１１—０８—１９　［基金项目］湛江师范学院青年教师校级项目（ＱＩ＿８Ｏ１）。０　［作者简介】袁晓（１９８２一），女，广东湛江人，湛江师范学院数学与计算科学学院讲师，硕士，从事计算数学研究。　・　ｌ６・　除了增加容量，Ｂｒ／ｔｅ　Ｐｏｗｅｒ还必须经营工厂；营运成本基于使用的容量．如果第ｔ年的需求量是Ｄ。兆瓦特，　第１年的总容量是　兆瓦特，那么按恒定美元计算的第ｔ年运营成本就是（云￡）０ｊ・　・４０万美元．　上，ｌ　（Ⅶ）假设每年存贮量的上限为ｌ０兆瓦特，每年每兆瓦特的电力的存贮费用是１０万美元．　（Ⅷ）基本上，虽然公司可以以每兆瓦特６０万美元的价格每年从邻近的电力公司购买５兆瓦特电力（按照　恒定美元），但是公司必须满足这年的所有需求．　需要解决的关键问题：　（１）如何预测未来ｌＯ年的需求量？　（２）何时增加容量？应当增加多少？　２模型的建立　２．１问题的分析　该公司主要解决的问题如下：（１）选择合适的预测方法预测未来ｌ０年的预测量；（２）确定在２０１１—２０２０年　中，何时建立新工厂，容量为多少；（３）哪些年份需要从邻近的电力公司购买电力，才能满足这些年的所有需求．　很明显，确定某年份建立新厂可以采用０—１变量，从而使该问题建立混合整数规划模型比较合适．　２．２问题的假设　（１）假设在ｌ０年的时间中，公司不考虑年通货膨胀率和折现率等货币折现问题，降低了决策系统的复杂　性，从而使得系统可行．（２）假设公司的电力需求量的数据具有可靠性和稳定性．（３）假设电力工厂不考虑折旧　率。并且相互独立．　２．３未来ｌ０年需求量的预测　通过观察２００１年到２０１０年该公司ｌＯ年的电力需求量，我们发现数据呈增长趋势，作出散点图如下：　图１　２００１—２０１０需求量　很明显，需求量呈线性增长趋势，考虑采用一次函数Ｙ＝ＯＡ；＋ｂ拟合预测，采用ＭＡＴＬＡＢ中的拟合工具箱　ｅｆｗｏｌ拟合出一次曲线表达式为），＝２．９９４ｘ＋３Ｏ．８８，作出图形如图２．　其中拟合的可决系数Ｒ２＝Ｏ．９９０８，说明拟合效果良好。预测出未来１０年的需求量如表２所示：　表２未来１Ｏ年需求量　年份　２０１１　０１２　２０ｌ３　２０１４　２Ｏ１５　预测量　６３．８１４　６６．８０８　６９．８０２　７２．７９６　７５．７９ｏ　年份　２Ｏ１６　２０ｌ７　２Ｏ１８　２０ｌ９　２０２０　预测量　７８．７８４　８１．７７８　８４．７７２　８７．７６６　９０．７６ｏ　・　１７・　图２一次函数拟合图　２．４非线性整数规划模型模型的建立　２．４．１考虑约束条件如下：　（１）每年贮存电量不超过ｌＯ兆瓦特；假设第ｉ年贮存量为ｖｔ，ｔ＝０，１，２，…，１Ｏ，其中假设　０＝０．则　１０，ｔ＝１，２，…，ｌＯ．　（２）每年至多能建造一个工厂；假设第ｔ年是否建造５、１Ｏ、Ｉ５、２０兆瓦特生产能力的工厂情况分别为　ｌ，　２，　ｆ３＇　ｆ４，当四者取值为０时，表示第￡年不修建工厂，当其中某一个为ｌ时，表示修建对应类型的工厂．每年　至多能建造一个工厂越是表示为　ｌｌ＋　ｔ２＋　ｌ３＋Ｘｔ４ｓ１，￡＝１，２，…，ｌ０．　（３）每年至多能从邻近的电力公司购买５兆瓦特的电力；假设每至多能从邻近的电力公司购买电力的数量　为　，则ｕｔ－＜－５，ｔ＝１，２，…，ｌＯ．　（４）第ｉ年生产量＋第ｉ年购买电力量＋第（ｉ一１）年贮存量一第ｉ年需求量≥第ｉ年贮存量；其中第ｔ年　生产量为６０＋　（５　１＋１０ｘｉ２＋１５ｘ　３＋２０ｘｆ４）＝６０＋５）２（　ｎ＋２ｘｆ２＋３ｘｆ３＋４ｘｆ４），贝０　６ｏ＋５∑（　ｎ＋２　２＋３　３＋４　ｆ４）＋ｕＩ＋　ｌ—ｌ—ｄｔ三兰：　，ｔ＝１，２，…，ｌ０．　（５）非负约束和０一ｌ变量约束．ｕｌ，　０，　ＩＩ，戈ｆ２，　，　４＝０或１，ｔ＝１，２，…，１Ｏ．　２．４．２目标函数　假设第ｔ年总费用为Ｃ（ｔ），第ｔ年建立新工厂的成本为　（ｔ），第ｔ年运营成本为Ｂ（ｔ），第ｔ年购买电力成　本为Ｄ（￡），第ｔ年库存成本为Ｅ（ｔ），第￡年降低幂定律运行成本为，（ｆ）．　考虑使得ｌ０年总费用最少为目标函数，其中第ｔ年的费用如下：　第ｔ年的总费用＝第ｔ年建立新工厂的成本＋第ｔ年运营成本＋第ｔ年购买电力成本＋第ｔ年库存成　本。　即Ｃ（￡）＝Ａ（‘）＋Ｂ（ｔ）＋Ｄ（ｚ）＋Ｅ（ｚ）＋Ｆ（ｔ），其中　Ａ（ｆ）：（　）。。　×ｌ８０ｏ，　）：　～×Ｄｔ×４０００００，　Ｄ（ｔ）＝６０ｏ０００×　，　Ｅ（ｔ）＝１０００００×仇．　则２０１１年到２０２０年这１Ｏ年的总费用ｃ为　Ｃ＝∑［Ａ（ｔ）＋　（ｔ）＋Ｄ（ｔ）＋Ｅ（ｔ）］　Ｉ　１　．　１　８　．　＝ｌ８０ｏ　（｝＝、１　　塾　堕詈堡　±　丝））　，　０‘　＋４０ｏ００ｏ　ｔ　ｌ＝　ｏ１【　／Ｃ）－Ａｔ　０＂Ｓ　ｘ　Ｄｒ＋６０００００　Ｉ＝１ＩＯ　＋ｌ　。　００ｏ００荟Ｉ＝１’ｌＯ　最后得非线性整数规划模型为：　ｃ州　８ｏｏ　１ｏ（　）０．８＋（　］．　６０＋５　￣（ｘｉｌ＋２　２＋３ｘ　＋４　４）＋　Ｉ＋　一ｌ—ｄｔ￣ｖｔ，　：ｌ聋　≤ｌ，　Ｓ１０，　ｌ　５，　，　ｌ　０，　ｔｌ，　ｌ２，　Ｉ３，　ｌ４　０　宅１，　￡＝１，２，…，ｌ０．　３模型的求解　对于０—１整数非线性规划没有统一有效的求解方法，这里先考虑将０—１型离散变量转化为一个等价的　连续型非线性的约束条件，再采用遗传算法中的ＧＥＮＯＣＯＰ算法求解．　３．１将０—１变量等价连续化　考虑到０—１整数非线性规划直接求解比较复杂，为了达到简化计算的目的，这里利用隋允康、贾志超［３］提　出的将０一ｌ整数线性规划连续化的方法将０—１变量转化为连续型变量．具体做法如下：　Ｘｔｌ，￣ｔ２，Ｘｔ３，Ｘｔ４＝０　１，ｔ　，２，…，　ｉｆ　（ｏ－ｔｊ　．　一　－＊ｉｔ　＜ｌ－－’ｔｒ　ｒ，）＝０，２　，…，ｌｏ，　：ｌ＇２＇３，４．　这样转化后，就将原来的０—１混合非线性整数规划模型转化为约束条件全部为线性的优化模型，方便采用遗　传算法计算．化简结果如下：　ｍｉｎＣ：１１ｌ８０ｏ　［（　＋２ｘｌ２＋３ｘＩ３＋４ｘｌ４）０。８＋（　）０。５×ＤＩ＋　＋　］，　６ｏ＋５￣２（　ｌ＋２　￡２＋３ｘｆ２＋４　ｆ４）＋Ｕｔ＋／Ａｔ－１一　三兰＝　，　ｉ：ｌ１，　１０，　Ｉ　５，　Ｈｌ，　Ｏ，　口　（　ｆｆ一　）＝０，　０　Ｉ￡　１，　ｔ＝１，２，…，１０；ｊ＝１，２，３，４．　其中ａ　ｉ＞０为给定正数．　３．２采用ＧＥＮＯＣＯＰ求解　线性约束的优化问题应用很广，人们对它作了很多研究，例如对其中的线性规划问题，就提出了单纯形法、　内点法等．对线性约束的非线性复杂函数的优化问题通常采用迭代法和演化算法，１９９２年，Ｍｉｃｈａｌｗｉｃｚ和　Ｊａｎｉｋｏｗ提出了用于求解具有线性约束的数值优化问题的遗传算法——ＧＥＮＯＣＯＰ（Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｎｕｍｅｒｉｃａｌ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ｆｏｒ　Ｃｏｎｓｔｒａｉｎｅｄ　Ｐｒｏｍｂｌｅｍ），经实际应用证明是一种比较好的方法．其主要算法步骤如下：　（１）初始化种群，群体规模Ⅳ＝１００，置ｔ＝０；　・　１９・　（２）以目标函数为适应值函数，计算上一步确定的所有个体的适应值，保留最优适应值的个体．　（３）算法终止条件，若ｔ＝５００，或者算法超过５０次迭代最优适应值不变，停止；否则，转下一步．　（４）选择，采用竞标赛选择，在［１，１００］内随机产生６ｏ个个体序号ｋｌ，ｋ２，…，ｋ６０，选取这６０个个体中适应值　函数最优的个体．　（５）交叉，采用算术交叉和启发式交叉。设ｒ、ｑ为［Ｏ，Ｉ］中的随机数，若ｒｓＰ　，ｑｓＰ　，则进行算术交叉操　作；若ｒ５ｐ　，Ｐ　＜ｑ　，则进行启发式交叉操作；若ｒ＞Ｐ。，不进行交叉操作．　（６）对交叉后的个体，以０．１的概率采用边界变异法变异个体．　（７）置ｔ＝ｌ＋１．转（２）．　采用Ｍａｔｌａｂ７．０编程，最终计算结果如下：　ｔ＝１６８时算法终止，最优总费用为万美元Ｃ＝４５８０２５０．３３８万美元，由　２ｌ＝ｌ，托｝＝１可知２０１２年、２０１６年　分别建立生产容量为１Ｏ、１５兆瓦特的工厂，又由　ｌ＝３．８１４，　＝４．９６４可知２０１１年、２０１５年分别购买了３．８１４、　４．９６４兆瓦特电力．　４结论　实验结果表明针对该问题建立的０—１混合非线性整数规划模型，将０—１变量连续化处理，再采用遗传算　法中的ＧＥＮＯＣＯＰ算法求解，能有效地解决该公司的容量扩展问题．　［参考文献】　［１］Ｗａｙｎｅ　ｗｉｎｓｔｏｎ，Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ（Ｆｏｕｒｔｈ　Ｅｄｉｉｔｏｎ）［Ｍ］．Ｄｉｖｉｓｉｏｎ　０ｆＴｈｏｍｓｏｎ　Ｌｅａｒｎｉｎｇ，２００４：８５９—８６０．　［２］刘明举．幂定律基础上的煤层瓦斯流动模型［盯．焦作工学院学报，１９９４０）：４６—４９．　［３］隋允康，贾志超．０—１线性规划的连续化及其遗传算法求解［Ｊ］．数学实践与认识，２０１０（６）：ｌｌ９—１２７．　［４］Ｍｉｃｈａｌｅｗｉｅｚ　Ｚ，Ｊａｎｉｋｏｗ　Ｃ．ＧＥＮＯＣＯＰ：Ａ　Ｇｅｎｅｔｉｃ　Ａ￣，ｏｎｔｈｍ　ｆｏｒ　Ｎｕｍｅｅａｌ　Ｏｐｔｉｍｉｚａｉｔｏｎ　Ｐｒｏｂｌｅｍ　ｗｉｔｈ　Ｌｉｎｅａｒ　Ｃｏｎｓｔｒａｉｎｓ［Ｊ］．Ｃｏｍｍｕｎｉｅａ．　ｉｔｏｎｓ　０ｆｔｈｅＡＣＭ，１９９２（３）：１４５—１７３．　田ｌｅ　Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　Ｇ肿ＣｏＰ　Ａｌｇｏｒｉｔｈｍ　ｉｎ　０—１　Ｎｏｎｌｉｎｅａｒ　Ｉｎｔｅｇｅｒ　Ｐｒｏｇｎｎｍａｌｎｇ　Ｍｏｄｅｌ　ＹＵＡＮ　Ｘｉａｏ，ＬＩ　Ｊｉｅ—ｒｉｎｇ，ＷＡＮＧ　Ｓｈｉ—ｑｉ　（Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔａｔｉｏｎ　Ｓｃｉｅｎｃｅ，Ｚｈａｎｊｉａｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈａｎｊｉｎｇ　ａ５２４０４８，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｔｈｅ　ｎｅｘｔ　１０一ｙｅａｒ　ｄｅｍａｎｄ　ｏｆ　ａ　ｃｏｍｐａｎｙ　ｆｏｒ　ｐｏｗｅｒ　ｅａｐａｃｉｔｙ　ｉｓ　ｆｉｔｔｅｄ　ｂｙ　ｍｏｎａｄｉｃ　ｌｉｎｅａｒ　ｒｅｇｒｅｓｓｉｏｎ　ｍｏｄｅ１．Ａ　ｍｏｄｅｌ　ｆｏｒ　０—１　ｎｏｎｌｉｎｅａｒ　ｉｎｔｅｇｅｒ　ｐ玎　ｎｇ　ｉｓ　ｂｕｉｌｔ，ａｎｄ　ｔｈｅ　０—１　ｖａｒｉａｂｌｅｓ　ｏｆ　ｈｅ　ｍｏｄｅｌｔ　ａｒｅ　ｄｉｓｐｏｓｅｄ　ｃｏｎｔｉｎｕ—　ｏｕｓｌｙ．Ｉｔ　ｉｓ　ｓｏｌｖｅｄ　ｂｙ　ｔｈｅ　ＧＥＮＯＣＯＰ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｌｉｎｅａｒ　ｉｆｔｔｉｎｇ；ｎｏｎｌｉｎｅａｒ　ｉｎｔｇｅｒｅ　ｐＩＤ｛　ｍｍｌｉｎｇ　ｍｏｄｅｌ；ＧＥＮＯＣＯＰ　ａｌｏｒｇｉｔｈｍ　・２０・