Suitability of genetic based exploration in the creative design process

Abstract

Finding creative solutions to design problems depends heavily on a fruitful exploration in early phases. Many aspects of evolutionary computation (EC) and in particular genetic algorithms (GA) make them highly suited as computational tools for discovering good solutions. This paper discusses specific aspects of the GA method which parallel traditional design methodologies described by creativity researchers including Gordon, deBono, Parnes, and Osborn among others. Because EC methods work with populations of ‘fairly good’ solutions, there is less danger that creativity will be harmed by design fixation, on one ‘best’ solution. An example application is demonstrated using the design of a small truss bridge. The solutions offered by the application are varied enough to allow the designer a choice of forms. At the same time, all of the solutions offered are ‘fairly good’. This demonstrates the aspects of EC which make it well suited for creative exploration of problems.     

动态环境下基于预测机制的多种群进化算法

提出一种动态环境下基于预测机制的多种群进化算法,将预测机制引入到动态进化算法的研究中,对算法所得的某些信息进行记忆,根据记忆序列构建预测模型,当环境发生变化时能够通过预测模型对动态环境进行预先判断.算法采用自组织侦查的多种群策略,多个子种群对搜索子空间进行局部搜索,主种群用于确定新的搜索子空间.在子种群的自适应调整、子种群间的拥挤操作等方面进行了改进,根据子种群所跟踪的最优解位置信息构建预测模型,当环境发生变化时通过预测及子种群的进化实现对动态环境的自适应跟踪.以移动峰问题为测试对象,实验结果表明新算法具有良好的处理动态问题的能力.     

关于进化算法记忆存储方法的探讨*

针对进化算法的不同个体表示,分析研究了基于进化个体或其特征的存储表示和基于进化种群的概率记忆存储表示两类存储方法.通过研制分析可以看出,有效的搜索历史记忆存储方法能很好进行数据的存储和管理.如果记忆的存储方法与进化算法的控制过程相配合,则整个进化算法会变得更加有效.     

A single front genetic algorithm for parallel multi-objective optimization in dynamic environments

This paper proposes a new parallel evolutionary procedure to solve multi-objective dynamic optimization problems along with some measures to evaluate multi-objective optimization in dynamic environments. These dynamic optimization problems appear in quite different real-world applications with actual socio-economic relevance. In these applications, the objective functions, the constraints, and hence, also the solutions, can change over time and usually demand to be solved online whilst the size of the changes is unknown. Although parallel processing could be very useful in these problems to meet the solution quality requirements and constraints, to date, not many parallel approaches have been reported in the literature. Taking this into account, we introduce a multi-objective optimization procedure for dynamic problems that are based on PSFGA, a parallel evolutionary algorithm previously proposed by us for multi-objective optimization. It uses an island model where a process divides the population among the remaining processes and allows the communication and coordination among the subpopulations in the different islands. The proposed algorithm makes an exclusive use of non-dominating individuals for the selection and variation operator and applies a crowding mechanism to maintain the diversity and the distribution of the solutions in the Pareto front. We also propose a model to understand the benefits of parallel processing in multi-objective problems and the speedup figures obtained in our experiments.     

约束动态免疫算法及对背包问题性能测试研究

借鉴人工免疫系统的记忆、动态识别等功能,提出一种约束动态免疫算法(CDIOA),并用于高维约束动态背包问题的求解。通过随机约束选择策略选择可行及非可行抗体,非可行抗体参与群体的进化;利用抗体修正策略确保进化群中有一定比例可行抗体,提高算法搜索功能;设计环境识别模块判断环境变化与否,建立环境记忆池保存较优秀记忆细胞,记忆细胞参与相似(相同)环境初始群的产生,加速算法在相似环境搜索速度。建立三种不同环境的动态背包问题作为标准测试实例,将CDIOA与已有的四种动态优化算法进行测试比较,结果表明:CDIOA对各测试问题在不同环境表现出较好的收敛性能,在相似环境能快速跟踪最优值。     

演化算法时间复杂性的趋势条件

计算时间复杂性是演化理论中的一个重大课题.将趋势分析引入演化算法的平均时间复杂性分析,可用于很广一类演化算法及许多问题.基于趋势分析,研究了确定演化算法时间复杂性的一些有用的趋势条件.这些条件应用于完全欺骗问题以验证其有效性.     

Analysing stability and investments in railway networks using advanced evolutionary algorithms

We consider a network of periodically running railway lines. Investments are possible to increase the speed and to improve the synchronisation of trains. The model also includes random delays of trains and the propagation of delays across the network. We derive a cost‐benefit analysis of investments, where the benefit is measured in reduced waiting time for passengers changing lines. We also estimate the actual mean waiting time simulating the train delays. This allows us to analyse the impact that an increasing synchronisation of the timetable has on its stability. Simulation is based on an analytical model obtained from queueing theory. We use sophisticated adaptive evolutionary algorithms, which send off avant‐garde solutions from time to time to speed up the optimisation process. As there is a high correlation between scheduled and estimated waiting times for badly synchronised timetables, we are even able to include the time consuming simulation into our optimisation runs.     

A low-cost evolutionary algorithm for the unit commitment problem considering probabilistic unit outages

This article presents a solution method to the unit commitment problem with probabilistic unit failures and repairs, which is based on evolutionary algorithms and Monte Carlo simulations. Regarding the latter, thousands of availability–unavailability trial time patterns along the scheduling horizon are generated. The objective function to be minimised is the expected total operating cost, computed after adapting any candidate solution, i.e. any series of generating/non-generating (ON/OFF) unit states, to the availability–unavailability patterns and performing evaluations by considering fuel, start-up and shutdown costs as well as the cost for buying electricity from external resources, if necessary. The proposed method introduces a new efficient chromosome representation: the decision variables are integer IDs corresponding to the binary-to-decimal converted ON/OFF (1/0) scenarios that cover the demand in each hour. In contrast to previous methods using binary strings as chromosomes, the new chromosome must be penalised only if any of the constraints regarding start-up, shutdown and ramp times cannot be met, chromosome repair is avoided and, consequently, the dispatch problems are solved once in the preparatory phase instead of during the evolution. For all these reasons, with or without probabilistic outages, the proposed algorithm has much lower CPU cost. In addition, if probabilistic outages are taken into account, a hierarchical evaluation scheme offers extra noticeable gain in CPU cost: the population members are approximately pre-evaluated using a small ‘representative’ set of the Monte Carlo simulations and only a few top population members undergo evaluations through the full Monte Carlo simulations. The hierarchical scheme makes the proposed method about one order of magnitude faster than its conventional counterpart.     

A multi-population electromagnetic algorithm for dynamic optimisation problems

This paper is derived from an interest in the development of approaches to tackle dynamic optimisation problems. This is a very challenging research area due to the fact that any approaches utilised should be able to track the changes and simultaneously seek for global optima as the search progresses. In this research work, a multi-population electromagnetic algorithm for dynamic optimisation problems is proposed. An electromagnetic algorithm is a population based meta-heuristic method which imitates the attraction and repulsion of the sample points. In order to track the dynamic changes and to effectively explore the search space, the entire population is divided into several sub-populations (referred as multi-population that acts as diversity mechanisms) where each sub-population takes charge in exploring or exploiting the search space. In addition, further investigation are also conducted on the combination of the electromagnetic algorithm with different diversity mechanisms (i.e. random immigrants, memory mechanism and memory based immigrant schemes) with the aim of identifying the most appropriate diversity mechanism for maintaining the diversity of the population in solving dynamic optimisation problems. The proposed approach has been applied and evaluated against the latest methodologies in reviewed literature of research works with respect to the benchmark problems. This study demonstrates that the electromagnetic algorithm with a multi-population diversity mechanism performs better compared to other population diversity mechanisms investigated in our research and produces some of the best known results when tested on Moving Peak Benchmark (MPB) problems.     

基于渗透原理迁移策略的并行遗传算法

通过分析影响并行遗传算法性能的诸多因素,以避免人为设置迁移代频、迁移率及迁移方向为问题的突破口,以减少通信量提高算法效率为主旨,提出一种基于渗透原理的迁移策略(Migration Scheme Based On Penetration,PMS)．PMS迁移策略源于渗透模型,引入渗透阈值控制相邻子群体的迁移,应用渗透原理自适应地确定迁移代频、迁移率及迁移方向,从而解决人为设置迁移代频、迁移率及迁移方向的关键问题,有效降低通信代价,进而提高算法效率．文中首先依据有限群体马尔可夫链模型对基于渗透原理的迁移策略算法的可行性进行了探讨,然后从理论角度给出了迁移代频期望、迁移率期望及通信代价,同时用实例验证了PMS在降低通信代价方面的巨大潜力．     

A Two-Level Function Evaluation Management Model for Multi-Population Methods in Dynamic Environments: Hierarchical Learning Automata Approach

ABSTRACT

The fitness evaluation (FE) management has been successfully applied to improve the performance of multi-population methods for dynamic optimisation problems (DOPs). In this work, we extend one of its variants to address DOPs which was recently proposed by the authors. The aim of our proposal is to increase the efficiency of the FE management. To this end, we propose a technique based on hierarchical learning automata that manages FEs at two level: at first level the algorithm decides which population should be executed, and at the second level it specifies the operation that should be performed by the selected population. A detailed experimental analysis shows the effectiveness of our proposal.     

一种协调勘探和开采的遗传算法：收敛性及性能分析

提出了一种新的遗传算法结构。在该结构中,每一代的新种群由保留种 群、繁殖种群的随机种群三部分组成,而它们的相对数量则由不同的参数进行控制,这体现了该算法在运行过程中对搜索空间勘探和开采操作的协调和权衡。通过把该算法建模为齐次的有限Markov链,该文证明了该算法具有全局收敛性。对试验数据的分析表明,该算法能够有效协调算法对问题解空间的勘探和开采操作,因而在处理复杂问题时表现出较高的性能。     

实值多种群遗传算法求解动态规划问题

研究利用遗传算法求解动态规划问题.实验采用实值多种群遗传算法,绕过复杂的数学推导,求解推车系统的最优控制序列u*(k).在遗传算法迭代过程中,染色体采用实值编码、多种群、多目标并行搜索,并利用留优策略加速搜索收敛速度,求解得最优控制序列u*(k).计算的目标函数值和数学解析解极值完全一致,证明了该方法的准确、高效.     

基于搜索能力均衡的人工蜂群算法

鉴于标准人工蜂群算法（ABC）局部开发能力不足;提出一种改进搜索策略的人工蜂群算法（IABC）。为提高ABC的局部开发能力;在其雇佣蜂阶段引入了一个新的具有最好个体引导的解搜索方程;为均衡ABC的搜索能力;在ABC跟随蜂阶段的搜索策略中引入了新的随机因素以增强ABC的全局探索能力;为了进一步平衡全局探索和局部开发能力;改进了ABC的侦察蜂搜索机制。为验证IABC的收敛效果;通过在12个复杂基准测试函数上的仿真实验并与其他算法相比较;发现IABC的收敛性能有显著提高。     

链式多种群多智能体进化算法

将多种群的进化方式和链式结构的动态邻域引入到多智能体进化算法中,提出了一种链式多种群多智能体进化算法.算法设置了多种群交互的演化结构.各种群中的智能体通过与其动态邻域智能体的竞争、合作及自学习操作来增加自身的能量;动态邻域的链式结构提高了算法的效率、降低了计算复杂度;多个种群之间的信息定期以一定的方式进行交互,增强了种群的多样性,减小了算法陷入局部最优的机率.理论分析和多个测试函数的仿真结果均表明:链式多种群多智能体进化算法在求解高维优化问题上具有很好的性能.     

A genetic algorithm for combined topology and shape optimisations

A method to find optimal topology and shape of structures is presented. With the first the optimal distribution of an assigned mass is found using an approach based on homogenisation theory, that seeks in which elements of a meshed domain it is present mass; with the second the discontinuous boundaries are smoothed. The problem of the optimal topology search has an ON/OFF nature and has suggested the employment of genetic algorithms. Thus in this paper a genetic algorithm has been developed, which uses as design variables, in the topology optimisation, the relative densities (with respect to effective material density) 0 or 1 of each element of the structure and, in the shape one, the coordinates of the keypoints of changeable boundaries constituted by curves. In both the steps the aim is that to find the variable sets producing the maximum stiffness of the structure, respecting an upper limit on the employed mass. The structural evaluations are carried out with a FEM commercial code, linked to the algorithm. Some applications have been performed and results compared with solutions reported in literature.