西安交通大学学报
西安交通大學學報
서안교통대학학보
JOURNAL OF XI'AN JIAOTONG UNIVERSITY
2009年
2期
29-32
,共4页
多目标进化%最优解集%非支配集%伪二叉树法则
多目標進化%最優解集%非支配集%偽二扠樹法則
다목표진화%최우해집%비지배집%위이차수법칙
针对多目标进化算法中如何提高非支配集构造效率的问题,提出了一种用伪二叉树法则构造多目标Pareto最优解集的方法.根据多目标解的性质,将解的比较结果分为支配、被支配以及不相关3种类型,再根据解的比较结果生成排序伪二叉树.在每一轮比较中,从进化群体中选出一个个体,将该个体与当前非支配集中的个体进行比较,淘汰被支配的个体,而未被淘汰的个体将插入到非支配集中第一个被淘汰个体的位置.依次进行,直到进化群体中的个体比较完毕,从而生成排序的伪二叉树.同时,在理论上证明了采用该方法获取的非支配集为目标进化群体的最大非支配集,分析得知其在最差情况下的时间复杂度为O(rN2/2).实验结果表明,当目标数较大时(r≥5),在构造非支配集的效率上伪二叉树法要明显优于Deb、Jensen算法及擂台赛法则.
針對多目標進化算法中如何提高非支配集構造效率的問題,提齣瞭一種用偽二扠樹法則構造多目標Pareto最優解集的方法.根據多目標解的性質,將解的比較結果分為支配、被支配以及不相關3種類型,再根據解的比較結果生成排序偽二扠樹.在每一輪比較中,從進化群體中選齣一箇箇體,將該箇體與噹前非支配集中的箇體進行比較,淘汰被支配的箇體,而未被淘汰的箇體將插入到非支配集中第一箇被淘汰箇體的位置.依次進行,直到進化群體中的箇體比較完畢,從而生成排序的偽二扠樹.同時,在理論上證明瞭採用該方法穫取的非支配集為目標進化群體的最大非支配集,分析得知其在最差情況下的時間複雜度為O(rN2/2).實驗結果錶明,噹目標數較大時(r≥5),在構造非支配集的效率上偽二扠樹法要明顯優于Deb、Jensen算法及擂檯賽法則.
침대다목표진화산법중여하제고비지배집구조효솔적문제,제출료일충용위이차수법칙구조다목표Pareto최우해집적방법.근거다목표해적성질,장해적비교결과분위지배、피지배이급불상관3충류형,재근거해적비교결과생성배서위이차수.재매일륜비교중,종진화군체중선출일개개체,장해개체여당전비지배집중적개체진행비교,도태피지배적개체,이미피도태적개체장삽입도비지배집중제일개피도태개체적위치.의차진행,직도진화군체중적개체비교완필,종이생성배서적위이차수.동시,재이론상증명료채용해방법획취적비지배집위목표진화군체적최대비지배집,분석득지기재최차정황하적시간복잡도위O(rN2/2).실험결과표명,당목표수교대시(r≥5),재구조비지배집적효솔상위이차수법요명현우우Deb、Jensen산법급뢰태새법칙.
