求解仿真优化问题的知识型启发式搜索方法

仿真优化研究基于仿真的目标优化问题,已经成为系统仿真和运筹学等领域共同关注的热点和前沿课题.针对离散事件动态系统仿真优化中的难点问题,提出了一种全新的知识型启发式搜索方法.采用知识模型和启发式搜索模型相结合的集成建模思路,以启发式搜索模型为基础,同时突出知识模型的作用,将启发式搜索模型和知识模型进行优化组合、优势互补,以提高启发式搜索技术的效率.基于期望值模型的数值仿真,验证了方法的可行性和有效性.仿真结果表明,无论是求解质量还是求解速度,都优于其它几种现有方法.研究结果表明,将知识模型合理地嵌入到现有启发式搜索方法中,可以有效地解决复杂的仿真优化问题.     

A Heuristic Genetic Algorithm for Solving Resource Allocation Problems

In the paper, a heuristic genetic algorithm for solving resource allocation problems is proposed. The resource allocation problems are to allocate resources to activities so that the fitness becomes as optimal as possible. The objective of this paper is to develop an efficient algorithm to solve resource allocation problems encountered in practice. Various genetic algorithms are studied and a heuristic genetic algorithm is proposed to ameliorate the rate of convergence for resource allocation problems. Simulation results show that the proposed algorithm gives the best performance.     

细菌觅食算法求解高维优化问题

针对细菌觅食优化算法中,以往的自适应步长公式引入参数过多,统一的经验性参数无法适应各类不同问题的情况,提出了改进的自适应步长公式,通过在步长公式中引入当前细菌的进化代数、寻优范围,并发挥当前最优细菌的引导作用,灵活的调整步长,真正达到自适应调整步长的目的;其次对高维优化问题进行分析,将其分为可分解可分组、不可分解可分组和不可分解不可分组三大类,针对不同类型的问题,采用不同的分组方式,降维、细化来求解,将复杂的问题简单化,极大的提高了求解的效率和精度。将改进的自适应步长公式应用于高维优化问题的求解方法中,通过对多个标准测试函数在多维空间特别是超高维空间（500维、800维、1000维）进行测试,并将其结果同其它算法进行比较,实验证明本文改进算法在寻得最优解的精度和效率上比其它改进方案有显著提高。     

一种求解数值优化问题的进化规划算法

针对进化规划算法收敛速度慢、容易早熟收敛等问题,提出一种基于探测变异的进化规划算法。该算法通过降维得到多个探测变异量,对个体进行探测变异,使个体始终向适应度好的方向进化,并利用自适应高斯变异标准差伸缩搜索空间,使个体跳出局部最优解。通过3个经典算例对其性能进行测试,实验结果证明该算法收敛速度快,求解质量高,可以解决早熟收敛等问题。     

求解约束优化问题的一种复合形遗传算法

研究约束优化问题是科学和工程应用领域经常会遇到的一类数学规划问题.现有的约束优化进化算法,通常的解决办法是将等式约束条件转化为成对的不等式约束条件来处理,转换会使得可行域的拓扑结构变化显著,直接影响了算法性能和解的精度.为解决上述问题,提出了一种改进的处理约束优化问题的新算法.新算法将约束优化问题转化为多目标优化问题,把复合形法嵌入到遗传算法中,通过将全局搜索和局部搜索机制有机地结合,利用遗传算法全局性好和复合形法快速高效的特点,以加快最优解的搜索进程.仿真结果表明,方法既有复合形法快速高效的特点,又有遗传算法全局性好的特点.与标准遗传算法相比,方法具有良好的求解约束优化性能和精度效果.     

动态Kriging优化算法求解昂贵约束优化问题

针对昂贵单目标约束优化中真实模型计算费时且现有算法收敛速度慢的问题,提出了动态Krging优化算法以提高计算效率.该算法首先将所有约束条件转换为一个约束函数,然后采用拉丁超立方体采样(LHS)法进行采样,分别建立真实模型目标函数和约束函数的Kriging代理模型,同时结合真实模型对代理模型估计进行误差矫正,采用非支配个体选择、保留和替换机制不断更新样本库和Kriging代理模型.最后将进化最优种群代入真实模型计算其最优值.通过13个标准函数测试表明该算法具有较高的精确度和稳健性,明显减少了真实模型的评价次数.     

求解PDPTW问题的快速启发式算法

提出了一种解决有时间窗口装卸货问题（PDPIW）的快速启发式算法．该算法基于局域搜索和随机扰动的思想,以减少车辆数目为主要目标,采用了启发式的搜索方法并加入了随机扰动以跳出局部最小点。该算法可以在很短的时间内显著地提高解的质量,这是仅以减少总路程为主要目标的局域搜索和现代启发式算法不能达到的。对标准算例的测试和与禁忌搜索算法计算结果的比较,表明该算法对于求解此类有时间窗口装卸货问题比传统的启发式算法在计算速度和减少车辆数目上更具优势。     

求解约束优化问题的改进元胞遗传算法

针对约束优化问题,提出一种改进元胞遗传算法.将自适应ε约束处理技术与元胞遗传算法结合,对于自适应ε约束处理技术中的截断进化代数,在其前期提出偏好性指标概念,随机选取满足约束条件较好的个体引导种群快速向可行域逼近,在其后期采用改进柯西变异算子避免陷入局部最优.基于一组标准测试函数进行测试,与其它算法进行对比,结果表明算法具有较好的收敛精度,且在高维函数中取得更优的结果,验证了算法的有效性与先进性.     

一种求解约束优化问题的线性进化算法

提出一种基于实数编码处理约束优化问题的线性算法,并对其复杂度和收敛性进行分析.该算法将约束优化问题的高维搜索空间通过线性变换映射到二维空间,在二维空间中探索原优化问题的解,从数学分析的角度给出一种线性适应度函数.算法中融入一种基于密度函数的交叉算子和变异算法,采用基于分级聚类的平均联接方式以维持Pareto最优解集个体数目.3组典型优化问题的测试表明,该算法是可行和有效的,解集分布的均匀性与多样性均较理想.     

A New Evolutionary Algorithm for Solving Many-Objective Optimization Problems

In this paper, we focus on the study of evolutionary algorithms for solving multiobjective optimization problems with a large number of objectives. First, a comparative study of a newly developed dynamical multiobjective evolutionary algorithm (DMOEA) and some modern algorithms, such as the indicator-based evolutionary algorithm, multiple single objective Pareto sampling, and nondominated sorting genetic algorithm II, is presented by employing the convergence metric and relative hypervolume metric. For three scalable test problems (namely, DTLZ1, DTLZ2, and DTLZ6), which represent some of the most difficult problems studied in the literature, the DMOEA shows good performance in both converging to the true Pareto-optimal front and maintaining a widely distributed set of solutions. Second, a new definition of optimality (namely, L-optimality) is proposed in this paper, which not only takes into account the number of improved objective values but also considers the values of improved objective functions if all objectives have the same importance. We prove that L-optimal solutions are subsets of Pareto-optimal solutions. Finally, the new algorithm based on L-optimality (namely, MDMOEA) is developed, and simulation and comparative results indicate that well-distributed L-optimal solutions can be obtained by utilizing the MDMOEA but cannot be achieved by applying L-optimality to make a posteriori selection within the huge Pareto nondominated solutions. We can conclude that our new algorithm is suitable to tackle many-objective problems.      

一种解函数优化问题的精英子空间演化算法

文献[1]提出了一种有效的求解优化问题的演化算法，算法简单易行，并能在较短时间内找到问题的最优解，在该算法的基础上，文中提出了一种精英子空间演化算法，在算法的杂交过程中，通过采用精英保存策略，增加父体的选择压力来加速算法的收敛，数值试验表明新算法比文献[1]中的算法具有更好的收敛性，能更快地找到优化问题的最优解。     

Immigrant Population Search Algorithm for Solving Constrained Optimization Problems

This article introduces the Immigrant Population Search Algorithm (IPSA) inspired by the pattern of human population migration to find better habitats. The algorithm is viewed as a new optimization method for solving constrained optimization problems, and it belongs to the set of population-based algorithms that are proposed for combinatorial optimization. In this algorithm, the life environment is the solution space of the problem. Every point of this space is a solution for the problem, which may be feasible or infeasible, and the quality of life at that point is the value of fitness function for that solution. Each population group tries to investigate feasible and better habitats. In other words, it tries to optimize the problem. After the algorithm steps are described, the efficiency of the algorithm is compared to that of three other metaheuristic algorithms that are used to optimize some mathematic problems. The results show that the proposed algorithm performs better than the other three methods.     

面向高维复杂多模态问题的教与学优化求解算法

针对教与学优化算法（Teaching-Learning-Based Optimization：TLBO）在求解一些高维多模态复杂优化问题时,存在种群容易过早陷入局部搜索,导致丢失全局最优解的问题,提出一种改进的TLBO优化算法（MTLBO）。该算法以更接近人类的学习方式,对标准TLBO中的“教”和“学”过程进行了改进,并引入了新的“自学”机制来加强学员的创新学习能力,从而有效提高了算法的全局探索能力。通过10个复杂的多模态优化问题测试表明,在求解复杂多模态问题方面,与5个具有优异性能的TLBO算法和3个经典的群智能计算方法(SaDE,CLPSO, NGHS)相比,本文算法具有全局搜索能力强,稳定性好等明显优势。     

基于遗传算法的最优化问题求解

遗传算法是一种有效的解决最优化问题的方法,在解决复杂的全局优化问题方面,遗传算法已得到了成功的应用。对遗传算法的基本步骤进行总结,通过最优化问题求解实例描述了遗传算法的具体运行过程,包括产生初始染色体、染色体评价、选择、交叉、变异等。分别应用VC和VB两种语言进行编程实现,结果表明,VC语言在运算效率和结果优度方面均比VB语言要好。     

求解QBF 问题的启发式调查传播算法

提出了一种启发式调查传播算法,并基于该算法设计了一种QBF(quantified Boolean formulae)求解器——HSPQBF(heuristic survey propagation algorithm for solving QBF)系统.它将Survey Propagation信息传递方法应用到QBF求解问题中.利用Survey Propagation作为启发式引导DPLL(Davis,Putnam,Logemann and Loveland)算法,选择合适的变量进行分支,从而可以减小搜索空间,并减少算法回退的次数.在分支处理过程中,HSPQBF系统结合了单元传播、冲突学习和满足蕴涵学习等一些优秀的QBF求解技术,从而能够提高QBF问题的求解效率.实验结果表明,HSPQBF无论在随机问题上还是在QBF标准测试问题上都有很好的表现,验证了调查传播技术在QBF问题求解中的实际价值.     

一种求解集装箱装载问题的启发式算法

所谓集装箱装载问题,就是将若干大小不同的长方体盒子装进一个大小已知的长方体容器,其目标是最大化容器的积裁率.对这一问题,国内外学者利用不同的哲学思想,提出了诸如遗传算法、模拟退火算法等求解算法.本文提出一种求解此问题的基于最大穴度优先原则的启发式算法.算法中使用了两个重要的策略:最大穴度原则和最小边度原则.用一些公开的算例对算法性能进行了实算测试,测试结果表明:算法所得结果的容器积载率高,是求解集装箱装载问题的有效算法.     

求解动态优化问题的多种群热力学遗传算法

多种群方法已被证明是提高演化算法动态优化性能的重要方法之一。提出了多种群热力学遗传算法（multi-population based thermodynamic genetic algorithm,MPTDGA）。该算法使用一个概率向量在热力学遗传算法迭代过程中不断演化优化与竞争学习,环境变化时分化成三个概率向量,并分别抽样产生原对偶和随机迁入三个子种群,依据这三个种群和记忆种群最好解的情况,选择新的工作概率向量进入新环境进行学习。在动态背包问题上的实验结果表明,MPTDGA比原对偶遗传算法跟踪最优解的能力更强,有很好的多样性,非常适合求解0-1动态优化问题。     

一种减小方差求解非光滑问题的随机优化算法

随机优化算法是求解大规模机器学习问题的高效方法之一.随机学习算法使用随机抽取的单个样本梯度代替全梯度,有效节省了计算量,但却会导致较大的方差.近期的研究结果表明:在光滑损失优化问题中使用减小方差策略,能够有效提高随机梯度算法的收敛速率.考虑求解非光滑损失问题随机优化算法COMID(compositeobjective mirror descent)的方差减小问题.首先证明了COMID具有方差形式的O(1/√T+σ²/√T)收敛速率,其中,T是迭代步数,σ²是方差.该收敛速率保证了减小方差的有效性,进而在COMID中引入减小方差的策略,得到一种随机优化算法α-MDVR(mirror descent with variance reduction).不同于Prox-SVRG(proximal stochastic variance reduced gradient),α-MDVR收敛速率不依赖于样本数目,每次迭代只使用部分样本来修正梯度.对比实验验证了α-MDVR既减小了方差,又节省了计算时间.     

适用于多峰函数优化问题的通用演化算法

本文在“两阶段子空间演化算法”的基础上加以改进,提出了一种解各种多峰函数优化问题的通用演化算法;并用五个复杂的函数进行了数值试验,得到了较好的结果。     

求解全局优化问题的混合自适应正交遗传算法

提出了一种基于正交实验设计的混合自适应正交遗传算法(hybrid self-adaptive orthogonal genetic algorithm,简称HSOGA)以求解全局优化问题,此算法利用正交实验设计方法设计交叉算子,并提出一种自适应正交交叉算子.该自适应正交交叉算子根据父代个体的相似度自适应地调整正交表的因素个数和对父代个体进行因素分割的位置,生成具有代表性的子代个体,以更好地搜索空间.此外,新算法利用自适应正交交叉算子生成均匀分布的初始种群,以保证初始群体的多样性.同时引入了局部搜索策略以提高算法局部搜索能力和收敛速度.通过14个高维的Benchmark函数验证了算法的通用性和有效性.