论文部分内容阅读
隐式目标优化问题是指优化目标不能用明确的数学函数表达的最优化问题。现实生活中的许多问题都可以看成隐式目标优化问题,例如服装设计、音乐创作、图像检索等。这类问题的优化目标一般是“满足人的某种需求”,往往涉及到人的偏好、直觉、经验、价值观、信仰等因素,因此难以量化。交互式进化算法是一种基于人的主观评价得到个体适应值的进化优化方法。作为解决隐式目标优化问题的主要方法,交互式进化算法得到了国内外许多学者的广泛关注。由于交互式进化算法中加入了人的因素,因此如何减轻用户疲劳并增强算法的求解效率,是一个十分迫切而有意义的课题。本论文从三个方面对交互式进化算法进行了深入的研究与探索,包括:用户交互方式研究、多用户交互式进化算法研究、交互式PBIL算法研究。具体而言,本论文的主要研究内容包括:(1)提出一种基于锦标赛选择的用户评估方式。该评估方式既减轻了传统的评分赋值方式给用户带来的心理压力,又避免了基于两个体对比的评估方式所需要的大量比较次数。当用户采用该评估方式对交互式进化算法中的个体进行评估时,首先,需要将种群划分为若干子种群;然后,用户选择出每个子种群中的优胜个体;接着,这些优胜个体参与下一轮的锦标赛。如此循环,直到选择出最后的优胜个体。此时,个体的适应值为该个体在锦标赛树中的高度。我们将基于锦标赛选择评估方式的交互式遗传算法应用于服装色彩优化系统,研究了种群规模和子种群规模的选择对算法性能的影响。然后,将该算法与基于两个体对比的交互式遗传算法进行对比实验,结果表明本文提出的算法在选择合适的子种群规模的情况下,能有效地减少用户的比较次数和算法收敛时间,从而减轻用户疲劳。(2)提出一种用户动态干预进化过程的操作——子染色体固定操作。这种操作能够防止进化过程中出现的优秀的基因片段被交叉算子和变异算子破坏,而且能够极大地缩小问题的搜索空间。由于引入了子染色体固定操作,传统的交叉和变异算子都可能失效,为此,我们给出了改进的交叉和变异算子。为验证子染色体固定操作的有效性,我们将基于子染色体固定操作的交互式遗传算法和传统的交互式遗传算法分别应用于服装设计系统,进行了对比实验。实验结果表明:子染色体固定操作能够加快交互式进化算法的收敛速度并提高设计结果的质量。(3)提出一种能满足大众化需求的多用户交互式遗传算法模型。该模型用群体评估代替单用户评估,即个体适应度的评估取决于多个用户的评估结果,而不是取决于单个用户。给出了算法的三个主要模块——种群初始化模块、单种群模块和多种群模块的详细设计。最后,将多用户交互式遗传算法和一般的单用户交互式遗传算法分别应用于服装设计系统进行对比实验,结果表明:多用户交互式遗传算法的设计结果能更好地满足多个用户的偏好和要求,因而能更好地满足大众化需求。(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的每次运行能找到多个不同的目标个体,因而是一种解决多峰隐式目标优化问题的有效算法。