文档介绍：中国科学技术大学
博士学位论文
求解隐式目标优化问题的交互式进化算法研究
姓名:尤海峰
申请学位级别:博士
专业:计算机应用技术
指导教师:王煦法
2011-04-25
摘要
摘要
隐式目标优化问题是指优化目标不能用明确的数学函数表达的最优化问
题。现实生活中的许多问题都可以看成隐式目标优化问题,例如服装设计、音
乐创作、图像检索等。这类问题的优化目标一般是“满足人的某种需求”,往往
涉及到人的偏好、直觉、经验、价值观、信仰等因素,因此难以量化。交互式
进化算法是一种基于人的主观评价得到个体适应值的进化优化方法。作为解决
隐式目标优化问题的主要方法,交互式进化算法得到了国内外许多学者的广泛
关注。由于交互式进化算法中加入了人的因素,因此如何减轻用户疲劳并增强
算法的求解效率,是一个十分迫切而有意义的课题。
本论文从三个方面对交互式进化算法进行了深入的研究与探索,包括:用
户交互方式研究、多用户交互式进化算法研究、交互式 PBIL 算法研究。具体
而言,本论文的主要研究内容包括:
(1) 提出一种基于锦标赛选择的用户评估方式。该评估方式既减轻了传统
的评分赋值方式给用户带来的心理压力,又避免了基于两个体对比的评估方式
所需要的大量比较次数。当用户采用该评估方式对交互式进化算法中的个体进
行评估时,首先,需要将种群划分为若干子种群;然后,用户选择出每个子种
群中的优胜个体;接着,这些优胜个体参与下一轮的锦标赛。如此循环,直到
选择出最后的优胜个体。此时,个体的适应值为该个体在锦标赛树中的高度。
我们将基于锦标赛选择评估方式的交互式遗传算法应用于服装色彩优化系统,
研究了种群规模和子种群规模的选择对算法性能的影响。然后,将该算法与基
于两个体对比的交互式遗传算法进行对比实验,结果表明本文提出的算法在选
择合适的子种群规模的情况下,能有效地减少用户的比较次数和算法收敛时间,
从而减轻用户疲劳。
(2) 提出一种用户动态干预进化过程的操作——子染色体固定操作。这种
操作能够防止进化过程中出现的优秀的基因片段被交叉算子和变异算子破坏,
而且能够极大地缩小问题的搜索空间。由于引入了子染色体固定操作,传统的
交叉和变异算子都可能失效,为此,我们给出了改进的交叉和变异算子。为验
证子染色体固定操作的有效性,我们将基于子染色体固定操作的交互式遗传算
法和传统的交互式遗传算法分别应用于服装设计系统,进行了对比实验。实验
结果表明:子染色体固定操作能够加快交互式进化算法的收敛速度并提高设计
结果的质量。
(3) 提出一种能满足大众化需求的多用户交互式遗传算法模型。该模型用
I
摘要
群体评估代替单用户评估,即个体适应度的评估取决于多个用户的评估结果,
而不是取决于单个用户。给出了算法的三个主要模块——种群初始化模块、单
种群模块和多种群模块的详细设计。最后,将多用户交互式遗传算法和一般的
单用户交互式遗传算法分别应用于服装设计系统进行对比实验,结果表明:多
用户交互式遗传算法的设计结果能更好地满足多个用户的偏好和要求,因而能
更好地满足大众化需求。
(4) 首次将基于群体的增量学习(Population-based Incremental Learning,
PBIL)算法应用于解决隐式目标优化问题,提出了交互式 PBIL(IPBIL)算法。
IPBIL 相对于传统的交互式进化算法的最大优势在于:其用户评估方式大大简
化。IPBIL 仅需要用户从种群中选择出最优个体,而不需要用户对每个个体都
进行评估。将 IPBIL 和 IGA 分别应用于服装设计问题,进行对比实验,结果表
明:虽然 IPBIL 比 IGA 需要更多的进化代数才能达到收敛,但是 IPBIL 收敛时
的时间消耗和鼠标点击数均大大小于 IGA,因而能够显著减轻用户疲劳。
(5) 为解决多峰隐式目标优化问题,在 IPBIL 算法基础上,进一步提出基
于多概率向量的交互式 PBIL(IPBIL with Multiple Probability Vectors,
IPBIL-MPV)算法。IPBIL-MPV 算法利用多个概率向量来扑捉不同的搜索方向,
使得算法的一次执行能够找到多个不同的目标解。将 IPBIL-MPV 应用于服装设
计问题,结果表明 IPBIL-MPV 的每次运行能找到多个不同的目标个体,因而是
一种解决多峰隐式目标优化问题的有效算法。

关键词:隐式目标优化问题,交互式进化算法,用户交互方式,多用户交互式
进化算法,基于群体的增量学习,多峰优化
II
Absract
Abstract
Opti