A novel genetic algorithm with different structure selection for circuit design optimization

In the traditional GA, the tournament selection for crossover and mutation is based on the fitness of individuals. This can make convergence easy, but some useful genes may be lost. In selection, as well as fitness, we consider the different structure of each individual compared with an elite one. Some individuals are selected with many different structures, and then crossover and mutation are performed from these to generate new individuals. In this way, the GA can increase diversification into search spaces so that it can find a better solution. One promising application of GA is evolvable hardware (EHW), which is a new research field to synthesize an optimal circuit. We propose an optimal circuit design by using a GA with a different structure selection (GAdss), and with a fitness function composed of circuit complexity, power, and signal delay. Its effectiveness is shown by simulations. From the results, we can see that the best elite fitness, the average fitness value of correct circuits, and the number of correct circuits with GAdss are better than with GA. The best case of optimal circuits generated by GAdss is 8.1% better in evaluation value than that by traditional GA.     

基于个体适应值灰模型的交互式遗传算法

为将交互式遗传算法应用于复杂的优化问题中,提出一种基于进化个体适应值灰模型预测的交互式遗传算法,为每代适应值序列建立灰模型,以衡量个体适应值评价的不确定性,通过对灰模型的灰预测,提取进化个体评价的可信度,在此基础上,给出进化个体适应值修正公式,将该算法应用于服装进化设计系统中。实验结果表明,该算法在每代都能获取更多的满意解。     

The multi-criteria minimum spanning tree problem based genetic algorithm

Minimum spanning tree (MST) problem is of high importance in network optimization and can be solved efficiently. The multi-criteria MST (mc-MST) is a more realistic representation of the practical problems in the real world, but it is difficult for traditional optimization technique to deal with. In this paper, a non-generational genetic algorithm (GA) for mc-MST is proposed. To keep the population diversity, this paper designs an efficient crossover operator by using dislocation a crossover technique and builds a niche evolution procedure, where a better offspring does not replace the whole or most individuals but replaces the worse ones of the current population. To evaluate the non-generational GA, the solution sets generated by it are compared with solution sets from an improved algorithm for enumerating all Pareto optimal spanning trees. The improved enumeration algorithm is proved to find all Pareto optimal solutions and experimental results show that the non-generational GA is efficient.     

A hybrid immigrants scheme for genetic algorithms in dynamic environments

Dynamic optimization problems are a kind of optimization problems that involve changes over time.They pose a serious challenge to traditional optimization methods as well as conventional genetic algorithms since the goal is no longer to search for the optimal solution(s) of a fixed problem but to track the moving optimum over time.Dynamic optimization problems have attracted a growing interest from the genetic algorithm community in recent years.Several approaches have been developed to enhance the performance of genetic algorithms in dynamic environments.One approach is to maintain the diversity of the population via random immigrants.This paper proposes a hybrid immigrants scheme that combines the concepts of elitism,dualism and random immigrants for genetic algorithms to address dynamic optimization problems.In this hybrid scheme,the best individual,i.e.,the elite,from the previous generation and its dual individual are retrieved as the bases to create immigrants via traditional mutation scheme.These elitism-based and dualism-based immigrants together with some random immigrants are substituted into the current population,replacing the worst individuals in the population.These three kinds of immigrants aim to address environmental changes of slight,medium and significant degrees respectively and hence efficiently adapt genetic algorithms to dynamic environments that are subject to different severities of changes.Based on a series of systematically constructed dynamic test problems,experiments are carried out to investigate the performance of genetic algorithms with the hybrid immigrants scheme and traditional random immigrants scheme.Experimental results validate the efficiency of the proposed hybrid immigrants scheme for improving the performance of genetic algorithms in dynamic environments.     

A slippery genetic algorithm-based process mining system for achieving better quality assurance in the garment industry

Due to the error-prone nature of garment manufacturing operations, it is challenging to guarantee the quality of garments. Previous research has been done to apply fuzzy association rule mining to determine process settings for improving the garment quality. The relationship between process parameters and the finished quality is represented in terms of rules. This paper enhances the application by encoding the rules into variable-length chromosomes for optimization with the use of a novel genetic algorithm (GA), namely the slippery genetic algorithm (sGA). Inspired by the biological slippage phenomenon in DNA replication, sGA allows changes to the chromosome lengths by insertion and deletion. During rule optimization, different parameters can be inserted to or removed from a rule, increasing the diversity of the solutions. In this paper, a slippery genetic algorithm-based process mining system (sGAPMS) is developed to optimize fuzzy rules with the aim of facilitating a comprehensive quality assurance scheme in the garment industry. The significance of this paper includes the development of a novel variable-length GA mechanism and the hybridization of fuzzy association rule mining and variable-length GAs. Though the capability of conventional GA in rule optimization has been proven, the diversity in the population is inherently limited by the fixed chromosome length. Motivated by this phenomenon, the sGA suggested in this paper allows various parameters to be considered in a rule, improving the diversity of the solutions. A case study is conducted in a garment manufacturing company to evaluate the sGAPMS. The results illustrate that better quality assurance can be achieved after rule optimization.     

Epigenomes: The missing heritability in human cardiovascular disease?

Cardiovascular disease is a tremendous burden on human health and results from malfunction of various networks of biological molecules in the context of environmental stress. Despite strong evidence of heritability, many common forms of heart disease (heart failure in particular) have not yielded to genome-wide association studies to identify causative mutations acting via the disruption of individual molecules. Increasing evidence suggests, however, that genetic variation in noncoding regions is strongly linked to disease susceptibility. We hypothesize that epigenomic variation may engender different chromatin environments in the absence of (or in parallel with) changes in protein or mRNA sequence and abundance. In this manner, distinct—genetically encoded—chromatin environments can exhibit distinct responses to environmental stresses that cause heart failure, explaining a significant portion of the altered susceptibility that is observed in human disease.     

A fuzzy self-tuning parallel genetic algorithm for optimization

The genetic algorithm (GA) is now a very popular tool for solving optimization problems. Each operator has its special approach route to a solution. For example, a GA using crossover as its major operator arrives at solutions depending on its initial conditions. In other words, a GA with multiple operators should be more robust in global search. However, a multiple operator GA needs a large population size thus taking a huge time for evaluation. We therefore apply fuzzy reasoning to give effective operators more opportunity to search while keeping the overall population size constant. We propose a fuzzy self-tuning parallel genetic algorithm (FPGA) for optimization problems. In our test case FPGA there are four operators—crossover, mutation, sub-exchange, and sub-copy. These operators are modified using the eugenic concept under the assumption that the individuals with higher fitness values have a higher probability of breeding new better individuals. All operators are executed in each generation through parallel processing, but the populations of these operators are decided by fuzzy reasoning. The fuzzy reasoning senses the contributions of these operators, and then decides their population sizes. The contribution of each operator is defined as an accumulative increment of fitness value due to each operator's success in searching. We make the assumption that the operators that give higher contribution are more suitable for the typical optimization problem. The fuzzy reasoning is built under this concept and adjusts the population sizes in each generation. As a test case, a FPGA is applied to the optimization of the fuzzy rule set for a model reference adaptive control system. The simulation results show that the FPGA is better at finding optimal solutions than a traditional GA.     

一种改进选择算子的遗传算法

遗传算法（Genetic Algorithm,GA）是一种模拟生物进化的智能算法,被广泛应用于求解各类问题。简单遗传算法（Simple GA）仅靠变异产生新的数值,常常存在搜索精确度不高的问题。针对这个问题,对SGA的选择算子进行改进,即把相似个体分在同一组中,以组为单位进行选择,并通过该组个体的特点进行高斯搜索生成新的群体。这样使得GA在搜索过程中不仅可以很好地保持个体的多样性,并且可以提高解的精确度。通过对11个函数（单峰和多峰）的仿真实验,证明了采用新的选择算子后,GA在求解问题的精确度上有了很大地改善。     

A comparative study on the performance of dissortative mating and immigrants-based strategies for evolutionary dynamic optimization

Traditional Genetic Algorithms (GAs) mating schemes select individuals for crossover independently of their genotypic or phenotypic similarities. In Nature, this behavior is known as random mating. However, non-random protocols, in which individuals mate according to their kinship or likeness, are more common in natural species. Previous studies indicate that when applied to GAs, dissortative mating - a type of non-random mating in which individuals are chosen according to their similarities - may improve their performance (on both speed and reliability). Dissortative mating maintains genetic diversity at a higher level during the run, a fact that is frequently observed as a possible cause of dissortative GAs’ ability to escape local optima. Dynamic optimization demands a special attention when designing and tuning a GA, since diversity plays an even more crucial role than it does when tackling static ones. This paper investigates the behavior of the Adaptive Dissortative Mating GA (ADMGA) in dynamic problems and compares it to GAs based on random immigrants. ADMGA selects parents according to their Hamming distance, via a self-adjustable threshold value. The method, by keeping population diversity during the run, provides an effective means to deal with dynamic problems. Tests conducted with dynamic trap functions and dynamic versions of Road Royal and knapsack problems indicate that ADMGA is able to outperform other GAs on a wide range of tests, being particularly effective when the frequency of changes is low. Specifically, ADMGA outperforms two state-of-the-art algorithms on many dynamic scenarios. In addition, and unlike preceding dissortative mating GAs and other evolutionary techniques for dynamic optimization, ADMGA self-regulates the intensity of the mating restrictions and does not increase the set of parameters in GAs, thus being easier to tune.     

基于改进遗传算法的无人机路径规划

针对传统遗传算法收敛速度慢、容易陷入局部最优、规划路径不够平滑、代价高等问题,提出了一种基于改进遗传算法的无人机(UAV)路径规划方法,该算法对遗传算法的选择算子、交叉算子和变异算子进行改进,从而规划出平滑、可飞的路径.首先,建立适合UAV田间信息获取的环境模型,并考虑UAV的目标函数与约束条件以建立适合本场景的更为复...     

云环境下方差定向变异遗传算法的任务调度

云环境下遗传算法（GA）的任务调度存在寻优能力差、结果不稳定等问题。对于上述问题,提出了一种基于方差与定向变异的遗传算法（V-DVGA）。在选择部分,在每一次迭代的过程中进行多次选择,利用数学方差来保证种群的多样性并扩大较优解的搜索范围。在交叉部分,建立新的交叉机制,丰富种群的多样性并提高种群整体的适应度。在变异部分,优化变异机制,在传统变异的基础上采用定向变异来提高算法的寻优能力。通过workflowSim平台进行云环境仿真实验,将此算法与经典的遗传算法和当前的基于遗传算法的工作流调度算法（CWTS-GA）进行比较。实验结果表明,在相同的设置条件下,该算法在执行效率、寻优能力和稳定性等方面优于其他两个算法,是一种云计算环境下有效的任务调度算法。     

IMMIGRANTS-ENHANCED MULTI-POPULATION GENETIC ALGORITHMS FOR DYNAMIC SHORTEST PATH ROUTING PROBLEMS IN MOBILE AD HOC NETWORKS

One of the most important characteristics in mobile wireless networks is the topology dynamics, that is, the network topology changes over time as a result of energy conservation or node mobility. Therefore, the shortest path (SP) routing problem turns out to be a dynamic optimization problem in mobile wireless networks. In this article, we propose to use multi-population genetic algorithms (GAs) with an immigrants scheme to solve the dynamic SP routing problem in mobile ad hoc networks, which are the representative of new generation wireless networks. Two types of multi-population GAs are investigated. One is the forking GA in which a parent population continuously searches for a new optimum and a number of child populations try to exploit previously detected promising areas. The other is the shifting-balance GA in which a core population is used to exploit the best solution found and a number of colony populations are responsible for exploring different areas in the solution space. Both multi-population GAs are enhanced by an immigrants scheme to handle the dynamic environments. In the construction of the dynamic network environments, two models are proposed and investigated. One is called the general dynamics model, in which the topologies are changed because the nodes are scheduled to sleep or wake up. The other is called the worst dynamics model, in which the topologies are altered because some links on the current best shortest path are removed. Extensive experiments are conducted based on these two models. The experimental results show that the proposed multi-population GAs with immigrants enhancement can quickly adapt to the environmental changes (i.e., the network topology changes) and produce high-quality solutions after each change.     

改进遗传优化的贝叶斯网络结构学习

针对贝叶斯网络结构学习提出了一种改进的遗传算法,和传统遗传算法相比,该改进算法针对贝叶斯网络结构学习问题增加了优化变异和修正非法图两个新的算子。新算子不但保持了贝叶斯网络学习的多样性和正确性,而且还能保证算法快速搜索到全局最优的网络结构。将该改进遗传算法用于贝叶斯网络结构学习的仿真结果表明,和传统K2算法、GS／GES算法、遗传算法和粒子群算法等算法相比,该算法具有更好的全局搜索能力和收敛速度。     

A framework for pedestrian comfort navigation using multi-modal environmental sensors

Environments significantly influence the sensation of pedestrians, while sensing and navigation technologies can help people improve their trip comfort. In this paper, we present an integrated framework, named NaviComf, which constructs pedestrian navigation systems to improve comfort in time varying environments taking into account the heterogeneous environmental factors. With NaviComf we aim to systematically provide solutions to the four key issues: (1) how to organize the huge amount of sensor data, (2) how to forecast future environmental information, (3) how to incorporate the heterogeneous environmental factors, and (4) how to select optimal paths in time varying environments. We have gathered sensor data of air temperature, relative humidity, and pedestrian congestion in real environments. We have also implemented a prototype system on the basis of the framework using the sensor data. Results of simulations and evaluations show that NaviComf can efficiently provide more comfortable paths as compared with the traditional navigation method.     

基于小波矩的改进遗传算法风切变识别

针对采用三次B样条小波矩提取的低空风切变图像的形状特征,提出了一种改进的遗传算法(GA)用于微下击暴流、低空急流、侧风以及顺逆风4种风切变的类型识别中。该算法中自适应交叉概率仅考虑了进化代数的影响,而变异概率强调个体与群体适应度的作用,使得在均匀把握群体演变方向时,极大程度地丰富种群的多样性。对由此改进算法选取的最优特征子集,采用三阶近邻分类器进行分类识别。实验结果表明,该自适应遗传算法操作方向性强,能快速收敛到全局最优解,稳定地提取出最优特征子集,最终使低空风切变的平均识别率达到97%以上,获取了较好的识别效果。     

Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms

In contrast to traditional job-shop scheduling problems, various complex constraints must be considered in distributed manufacturing environments; therefore, developing a novel scheduling solution is necessary. This paper proposes a hybrid genetic algorithm (HGA) for solving the distributed and flexible job-shop scheduling problem (DFJSP). Compared with previous studies on HGAs, the HGA approach proposed in this study uses the Taguchi method to optimize the parameters of a genetic algorithm (GA). Furthermore, a novel encoding mechanism is proposed to solve invalid job assignments, where a GA is employed to solve complex flexible job-shop scheduling problems (FJSPs). In addition, various crossover and mutation operators are adopted for increasing the probability of finding the optimal solution and diversity of chromosomes and for refining a makespan solution. To evaluate the performance of the proposed approach, three classic DFJSP benchmarks and three virtual DFJSPs were adapted from classical FJSP benchmarks. The experimental results indicate that the proposed approach is considerably robust, outperforming previous algorithms after 50 runs.     

基于混合选择和动态变异的基因表达式编程

基因表达式编程（GEP）是一种基于基因型和表现型的新型遗传算法,目前被广泛应用在函数发现、时间序列预测和分类等领域。传统GEP算法采用轮盘赌方式来选择种群个体,其择优强度过大,易导致个体多样性减弱,产生“近亲繁殖”;种群个体的变异概率固定,变异幅度不能动态地适应每代的进化结果,影响进化效率。针对上述两个缺陷,本文对传统GEP做出两点改进：作者采用混合选择策略,以维持进化过程中个体的多样性,避免“近亲繁殖”;引入动态变异思想,使种群在进化过程中能根据自身适应性的高低来动态调整个体的变异概率,以最大限度地保留高适应度基因片段,消除低适应度基因片段。通过实验,本文验证了两项改进的有效性。     

基于"优胜劣汰"原则的差异算子

借鉴生物学中“优胜劣汰”的原则,引入一种新的遗传算子,从而对传统的遗传算法（GA）进行改进.该算子的引入达到了扩大搜索空间、提高收敛速度、保持群体中个体多样性的目的.通过函数优化测试,结果表明：算子提高了GA对全局最优解的搜索能力和收敛速度.进一步对其相关参数设置的研究,将会使GA在众多实际的优化问题上具有更广泛的应用前景.     

基于GA的飞行员模拟机排班问题求解

飞行员模拟机复训问题是一个多目标、多资源约束的排班问题,具有较高的复杂度,传统遗传算法无法有效求解该问题。为此,提出一种新的遗传算法,利用基因适应度对交叉、选择操作进行改进,以提高种群的多样性和进化性能。在仿真数据和真实数据上的实验结果表明,该算法有效提高了解的精度,加快了种群的收敛速度。     

Chaotic populations in genetic algorithms

We set two objectives for this study: one is to emulate chaotic natural populations in GA (Genetic Algorithms) populations by utilizing the Logistic Chaos map model, and the other is to analyze the population fitness distribution by utilizing insect spatial distribution theory. Natural populations are so dynamic that one of the first experimental evidences of Chaos in nature was discovered by a theoretical ecologist, May (1976, Nature, 261,459–467)[30], in his analysis of insect population dynamics. In evolutionary computing, perhaps influenced by the stable or infinite population concepts in population genetics, the status quo of population settings has dominantly been the fixed-size populations. In this paper, we propose to introduce dynamic populations controlled by the Logistic Chaos map model to Genetic Algorithms (GA), and test the hypothesis – whether or not the dynamic populations that emulate chaotic populations in nature will have an advantage over traditional fixed-size populations.The Logistic Chaos map model, arguably the simplest nonlinear dynamics model, has surprisingly rich dynamic behaviors, ranging from exponential, sigmoid growth, periodic oscillations, and aperiodic oscillations, to complete Chaos. What is even more favorable is that, unlike many other population dynamics models, this model can be expressed as a single parameter recursion equation, which makes it very convenient to control the dynamic behaviors and therefore easy to apply to evolutionary computing. The experiments show result values in terms of the fitness evaluations and memory storage requirements. We further conjecture that Chaos may be helpful in breaking neutral space in the fitness landscape, similar to the argument in ecology that Chaos may help the exploration and/or exploitation of environment heterogeneity and therefore enhance a species’ survival or fitness.