基于遗传算法的一类NP-Hard网络规划求解.pdfVIP

增 刊 浙 江 大 学 学 报(自然科学版) Suppl…。 22墅堡§旦 』璺坚￡垦§!Ql兰b!亚e璺g型翌i∑!!!i!z!翌：!：：：!曼!：竺!! !!!!!!!§ 基于遗传算法的一类NP—Hard 网络规划求解‘ 叶 剑 曲润涛 席裕庚 (上海交通大学自动化研究所．上海．200030) 摘要 规划问题中有一类难以用常规方法求解的NP．Hard问题．并且这类问题有着广泛的实际 应用背景，因此对NP—Hard问题的有效求解有很重要的意义．遗传算法是一种具有并行计算特 性的随机化有哪些信誉好的足球投注网站算法，不依赖于同题的梯度信息．本文运用遗传算法对一类网络规划NP—Hard 问题进行求解．仿真结果表明算法是有效的． 关键词；规划；NP—Hard问题；遗传算法 中围法分类号：TP3lI．5 0引言 在网络规划中有一类不能用任何已知多项式算法求解的问题通常称为组合规划中的 题，这类问题有着广泛的实用背景，如通讯网络规划o]，生产过程调度r”等．这些问题的主要 特点是含有大量的0，1规划变量．在实际应用中，对于NP-Hard问题一般采用启发式方法 进行求解或添加一些假设条件使之转化为非NP—Hard问题进行求解．但是基于经验的启发 式方法过于依赖经验而通用性和鲁棒性不强．而利用假设条件进行NP。Hard问题到非NP— Hard问题的转化在实际规划中不一定可行．因此对NP—Hard问题有效求解的研究就显得 十分重要． 考虑以下类型的有广泛实际应用背景的NP—Hard网络规划问题： P： minCost (1) N i Cost=∑∑b％b=o，1 t (2) i--1 j--1 Ho加≤％ i，j一1，…，N (3) ·国家科委基础研究基金资助 560 浙 江 大 学 学 报t自然科学版) 1998年 其中Cost为网络总建设代价，Ⅳ为网络总节点数，b为0，1变量，^，等于I时表明在节点i和 节点j间要规划一条线路，为线路b的代价，Hopu为节点f到节点J要经过的最小中转节 点数，％为相应约束常数． 式(1)和式(2)为规划问题P的优化目标，即网络建设代价最低；式(3)为网络性能要求 约束，即两节点间的最小路径约束．规划问题P可以用来反映许多实际问题，如通讯网络建 设中的线路规划，交通运输网络规划等． 规划问题P在图论中没有有效的算法，为了对规划问题P有效求解，有必要考虑采用一 些新型的优化工具．遗传算法(Genetic 具有并行特征的有哪些信誉好的足球投注网站算法，并已成功地运用于一些大规模的问题的求解．本文试图运用遗传 算法这一新型工具，对NP—Hard问题P进行有效的求解．针对网络规划的特性，我们为规划 问题P设计了不同与一般一维编码方式的二维编码，并成功地运用于问题P的有效求解． 1 遗传算法 遗传算法是由美国J．Holland教授提出的一类随机化有哪些信誉好的足球投注网站算法，它模拟生物界中的自 然选择和遗传机制，通过群体有哪些信誉好的足球投注网站策略和个体问信息交换在解空间中进行最优点的有哪些信誉好的足球投注网站．因 为遗传算法不依赖于梯度信息，并且隐含有并行算法机制，所以特别适合于解决传统方法难 以解决的问题． 1．1 遗传算法基本要素 遗传算法包括的要素有；编码，适应度函数计算，初始群体生成，遗传操作，算法参数设 计等． 编码的目的是将优化问题的解空间转化为遗传算法易于操作的编码空间．一般编码方 式模仿生物的染色体结构，进行串型编码．适应度函数是一种评价函数，用于评价个体在整 个群体中的生存能力．基本遗传算法初始群体的生成一般应该是随机的，但为了使遗传算法