改进NSGA—II终止判断准则

在基于进化算法的多目标优化中,往往是通过设置最大进化代数来确定算法何时终止。但是,如果最大进化代数设置太大,会增加许多不必要的计算量,设置太小可能得不到理想的结果。为了解决上述问题,提出一种改进的终止判断准则,通过该终止判断准则,即使在最大进化代数设置得非常大的情况下,只要连续几次获得的相隔一定进化代数的Pareto优解集的种群距离均小于给定的阈值,算法即可终止,并得到理想的结果,算法不再继续计算直到进化到最大进化代数后才终止。从仿真结果可以看出,通过终止判断准则,不仅降低了进化代数,减少了计算量,证实了新终止判断准则可行。     

交互式进化计算中保持用户理性的最大进化代数

交互式进化计算中用户保持理性是算法全局收敛的重要条件,为确保用户保持理性,必须设计合理的最大进化代数.文中首先提出3类最大进化代数,其次,结合6种常见的适应度赋值方法分别研究最大进化代数的定量计算方法.理论分析和实验都表明,采用最值赋值和分等级赋值方法不仅切实可行,而且可以让用户在较大的代数内保持理性状态.文中研究为选择合适的适应度赋值方法提供参考依据.     

Bounded Model Checking for Probabilistic Computation Tree Logic

为了缓解概率计算树逻辑模型检测中的状态空间爆炸问题,提出了概率计算树逻辑的限界模型检测技术.该技术首先定义概率计算树逻辑的限界语义,并证明其正确性;之后,通过实例说明在传统限界模型检测中,以路径长度作为判断检测过程终止的标准已经失效,基于数值计算中牛顿迭代法的终止准则,设计了新的终止判断标准;然后提出基于线性方程组求解的限界模型检测算法;最后,通过3个测试用例说明,概率计算树逻辑限界模型检测方法在反例较短的情况下能够快速完成检测过程,而且比概率计算树逻辑的无界模型检测算法所需求得的状态空间要少.     

概率计算树逻辑的限界模型检测

为了缓解概率计算树逻辑模型检测中的状态空间爆炸问题,提出了概率计算树逻辑的限界模型检测技术.该技术首先定义概率计算树逻辑的限界语义,并证明其正确性;之后,通过实例说明在传统限界模型检测中,以路径长度作为判断检测过程终止的标准已经失效,基于数值计算中牛顿迭代法的终止准则,设计了新的终止判断标准;然后提出基于线性方程组求解的限界模型检测算法;最后,通过3个测试用例说明,概率计算树逻辑限界模型检测方法在反例较短的情况下能够快速完成检测过程,而且比概率计算树逻辑的无界模型检测算法所需求得的状态空间要少.     

方向性多层抽样继承排除全搜索算法

运动估计是视频压缩中的关键技术,是视频编码中的主要开销.全搜索算法是最简单可靠的块匹配算法.本文在传统全搜索算法的基础上,提出一种方向性多层抽样继承排除全搜索算法(DMSSEA).本文算法通过数理统计的方法设置判别条件,在全搜索中引入提前终止;并通过抽样计算降低计算量,提高计算灵活度;通过分层判别提高判别效率;通过对图像方向性的利用,提高了终止效率.该算法在保证运动估计全局最优的同时大大减少了搜索点数,提供高清晰度的视频编码.     

进化计算优化效率的定量评价

进化计算实现时选用的进化算子不同,其计算的时间复杂度和寻优能力也不同.为了对进化计算优化效率进行定量评价,本文提出"优化平均截止时间"和"优化截止时间分布熵"两个概念,并以此作为评价准则.通过选用有代表性的基准测试函数,应用本文提出的评价准则对实数编码中典型的交叉算子进行大量测试,评价结果与理论分析完全一致,不仅证实本文提出的评价准则是正确有效的,而且为科学合理地选择算子及其算法提供理论依据.同时本文构造的算法可直接用于求解工程优化问题.     

分布式系统可靠性的一种计算方法

分析了分布式程序可靠性问题及其在分布式系统应用时的局限性,提出了分布式系统程序可靠性的计算问题.通过采用ECP分解算法对连接矩阵进行迭代分解并实时判断终止条件,可以直接计算出分布式系统可靠性结果.同时对算法中使用的存储结构进行优化,使得算法占用较少的内存.最后给出了例子来论证算法.     

有界闭连通域上的非线性循环终止性分析

运用计算机代数中的Groebner基理论,对有界闭连通域上的单重非线性循环程序的终止性问题进行研究,建立了可计算的终止性判定算法. 该算法将这类循环的终止性判定问题归约为有无不动点的判定问题.     

基于总空闲时间增量的无等待流水调度混合遗传算法

将NP-难的最小化最大完工时间无等待流水调度问题等价转化为最小化总空闲时间的问题,改变传统求解调度序列目标函数的模式,通过目标函数变化量判断新解的优劣,大大降低算法所需计算时间.分析启发式算法基本操作和进化算子的总空闲时间增量性质,设计基本总空闲时间增量法以快速评估新产生解的质量.提出混合遗传算法IHGA(increment based hybrid genetic algorithm)求解该问题,构造相应初始种群生成方法和进化算子,提出进化概率动态更新策略和种群收敛判断与再生机制;算法混合了迭代改进局部搜索以进一步提高解的质量,基于120个经典Benchmark实例,将IHGA与目前求解该问题的有效算法RAJ,GR,SA2,TSM和FCH进行比较,实验结果表明:IHGA在性能方面优于其他,计算效率方面优于SA2和TSM,略逊于GR,RAJ和FCH.     

基于可靠度的循环冗余校验算法

针对循环冗余校验(CRC)准则在信道条件恶化时可能使译码出现较大迭代次数及错误的问题,提出了基于可靠度的迭代停止算法及重传算法。首先,每次迭代后,计算本次译码中间结果的可靠度,通过判断其是否达到阈值来实现迭代的提前结束;然后,将具有最大可靠度的中间结果保存并作为最终译码结果;最后,每次译码后,通过判断最大可靠度是否低于重传阈值来决定是否重传,通过至多3次传输的译码结果来计算最佳译码结果。仿真结果表明,在信噪比低于1.2 dB时,与CRC准则相比,迭代停止算法能在不增加迭代次数的基础上减少1或2个比特错误,重传算法能进一步减少至少2个比特错误,基于可靠度的算法可以实现更少的误比特数和迭代次数。     

Multiobjective evolutionary algorithms for electric power dispatch problem

The potential and effectiveness of the newly developed Pareto-based multiobjective evolutionary algorithms (MOEA) for solving a real-world power system multiobjective nonlinear optimization problem are comprehensively discussed and evaluated in this paper. Specifically, nondominated sorting genetic algorithm, niched Pareto genetic algorithm, and strength Pareto evolutionary algorithm (SPEA) have been developed and successfully applied to an environmental/economic electric power dispatch problem. A new procedure for quality measure is proposed in this paper in order to evaluate different techniques. A feasibility check procedure has been developed and superimposed on MOEA to restrict the search to the feasible region of the problem space. A hierarchical clustering algorithm is also imposed to provide the power system operator with a representative and manageable Pareto-optimal set. Moreover, an approach based on fuzzy set theory is developed to extract one of the Pareto-optimal solutions as the best compromise one. These multiobjective evolutionary algorithms have been individually examined and applied to the standard IEEE 30-bus six-generator test system. Several optimization runs have been carried out on different cases of problem complexity. The results of MOEA have been compared to those reported in the literature. The results confirm the potential and effectiveness of MOEA compared to the traditional multiobjective optimization techniques. In addition, the results demonstrate the superiority of the SPEA as a promising multiobjective evolutionary algorithm to solve different power system multiobjective optimization problems.     

多目标动态规划时段轮换并行算法

针对SIMD和MIMD结构的并行机提出多目标动态规划时段轮换并行算法,多目标动 态规划的时段轮换迭代算法,将全过程优化问题转化成子过程优化问题,然后在子过程非劣解 集中寻找全过程非劣解.这样,将多目标动态规划内存不足的问题转化成时间问题,然后利用 并行机超高速运算的优势来有效地解决内存不足问题.通过时间复杂性、加速比分析及实例. 说明了算法的有效性及优越性.     

基于数据仓库的多目标优化遗传算法

基于数据仓库的多目标优化遗传算法为解决多目标优化问题提供了有效的途径。其基本思想是:为求Pareto最优解的多目标优化遗传算法建立一个数据仓库,将进化过程中所产生的每一代Pareto最优解放入数据仓库中,在每一代先对数据仓库中的所有个体进行求Pareto最优解运算,淘汰掉劣解,再进行个体间的欧氏距离运算,将小于指定值的其中一个个体作为劣解处理。大量的计算机仿真计算表明,这种算法不仅能够有效地避免交叉或变异操作对Pareto最优解产生的破坏,而且进化速度极快,算法稳定,一般只需20￣40代的运算,即可得到分布广泛的Pareto最优解。     

一种带约束的多目标服务质量路由算法

多约束服务质量(QoS)路由是要求在多个约束条件下计算满足所有独立限制条件的可行路径．将这种NPC问题转化为一种带约束条件的多目标优化问题，根据多目标遗传算法的智能优化原理，提出一种多目标QoS路由算法来产生一组最优非劣路由．理论分析和实验结果表明，使用带约束的多目标遗传算法是解决多约束QoS路由的有效途径，能对提高网络性能起到重要作用．     

采用遗传算法求解多跳分组无线网服务质量路由优化模型

采用多目标遗传算法来确定多跳无线网服务质量路由优化问题的Pareto最优解集。通过计算表明，多目标遗传算法能够在一次运行中搜索到优化问题的近似Pareto最优解集，这为决策者进行目标折衷决策提供了充分的依据，此算法是有效可行的。     

Multiobjective optimization and multiple constraint handling withevolutionary algorithms. II. Application example

For part I see ibid., 26-37. The evolutionary approach to multiple function optimization formulated in the first part of the paper is applied to the optimization of the low-pressure spool speed governor of a Pegasus gas turbine engine. This study illustrates how a technique such as the multiobjective genetic algorithm can be applied, and exemplifies how design requirements can be refined as the algorithm runs. Several objective functions and associated goals express design concerns in direct form, i.e., as the designer would state them. While such a designer-oriented formulation is very attractive, its practical usefulness depends heavily on the ability to search and optimize cost surfaces in a class much broader than usual, as already provided to a large extent by the genetic algorithm (GA). The two instances of the problem studied demonstrate the need for preference articulation in cases where many and highly competing objectives lead to a nondominated set too large for a finite population to sample effectively. It is shown that only a very small portion of the nondominated set is of practical relevance, which further substantiates the need to supply preference information to the GA. The paper concludes with a discussion of the results     

Solving Multitrip Pickup and Delivery Problem With Time Windows and Manpower Planning Using Multiobjective Algorithms

The multitrip pickup and delivery problem with time windows and manpower planning (MTPDPTW-MP) determines a set of ambulance routes and finds staff assignment for a hospital. It involves different stakeholders with diverse interests and objectives. This study firstly introduces a multiobjective MTPDPTW-MP (MO-MTPDPTWMP) with three objectives to better describe the real-world scenario. A multiobjective iterated local search algorithm with adaptive neighborhood selection (MOILS-ANS) is proposed to solve the problem. MOILS-ANS can generate a diverse set of alternative solutions for decision makers to meet their requirements. To better explore the search space, problem-specific neighborhood structures and an adaptive neighborhood selection strategy are carefully designed in MOILS-ANS. Experimental results show that the proposed MOILS-ANS significantly outperforms the other two multiobjective algorithms. Besides, the nature of objective functions and the properties of the problem are analyzed. Finally, the proposed MOILS-ANS is compared with the previous single-objective algorithm and the benefits of multiobjective optimization are discussed.      

A problem space genetic algorithm in multiobjective optimization

In this study, a problem space genetic algorithm (PSGA) is used to solve bicriteria tool management and scheduling problems simultaneously in flexible manufacturing systems. The PSGA is used to generate approximately efficient solutions minimizing both the manufacturing cost and total weighted tardiness. This is the first implementation of PSGA to solve a multiobjective optimization problem (MOP). In multiobjective search, the key issues are guiding the search towards the global Pareto-optimal set and maintaining diversity. A new fitness assignment method, which is used in PSGA, is proposed to find a well-diversified, uniformly distributed set of solutions that are close to the global Pareto set. The proposed fitness assignment method is a combination of a nondominated sorting based method which is most commonly used in multiobjective optimization literature and aggregation of objectives method which is popular in the operations research literature. The quality of the Pareto-optimal set is evaluated by using the performance measures developed for multiobjective optimization problems.     

Dynamic multiobjective optimization problems: test cases, approximations, and applications

After demonstrating adequately the usefulness of evolutionary multiobjective optimization (EMO) algorithms in finding multiple Pareto-optimal solutions for static multiobjective optimization problems, there is now a growing need for solving dynamic multiobjective optimization problems in a similar manner. In this paper, we focus on addressing this issue by developing a number of test problems and by suggesting a baseline algorithm. Since in a dynamic multiobjective optimization problem, the resulting Pareto-optimal set is expected to change with time (or, iteration of the optimization process), a suite of five test problems offering different patterns of such changes and different difficulties in tracking the dynamic Pareto-optimal front by a multiobjective optimization algorithm is presented. Moreover, a simple example of a dynamic multiobjective optimization problem arising from a dynamic control loop is presented. An extension to a previously proposed direction-based search method is proposed for solving such problems and tested on the proposed test problems. The test problems introduced in this paper should encourage researchers interested in multiobjective optimization and dynamic optimization problems to develop more efficient algorithms in the near future.     

An MO‐GVNS algorithm for solving a multiobjective hybrid flow shop scheduling problem

This paper addresses the multiobjective hybrid flow shop (MOHFS) scheduling problem. In the MOHFS problem considered here, we have a set of jobs that must be performed in a set of stages. At each stage, we have a set of unrelated parallel machines. Some jobs may skip stages. The evaluation criteria are the minimizations of makespan, the weighted sum of the tardiness, and the weighted sum of the earliness. For solving it, an algorithm based on the multiobjective general variable neighborhood search (MO‐GVNS) metaheuristic, named adapted MO‐GVNS, is proposed. This work also presents and compares the results obtained by the adapted MO‐GVNS with those of four other algorithms: multiobjective reduced variable neighborhood search, nondominated sorting genetic algorithm II (NSGA‐II), and NSGA‐III, and another MO‐GVNS from the literature. The results were evaluated based on the Hypervolume, Epsilon, and Spacing metrics, and statistically validated by the Levene test and confidence interval charts. The results showed the efficiency of the proposed algorithm for solving the MOHFS problem.