Hybrid Multipopulation Cellular Genetic Algorithm and Its Performance

The selection pressure of genetic algorithm reveals the degree of balance between the global exploration and local optimization.A novel algorithm called the hybrid multi-population cellular genetic algorithm(HCGA)is proposed,which combines population segmentation with particle swarm optimization(PSO).The control parameters are the number of individuals in the population and the number of subpopulations.By varying these control parameters,changes in selection pressure can be investigated.Population division is found to reduce the selection pressure.In particular,low selection pressure emerges in small and highly divided populations.Besides,slight or mild selection pressure reduces the convergence speed,and thus a new mutation operator accelerates the system.HPCGA is tested in the optimization of four typical functions and the results are compared with those of the conventional cellular genetic algorithm.HPCGA is found to significantly improve global convergence rate,convergence speed and stability.Population diversity is also investigated by HPCGA.Appropriate numbers of subpopulations not only achieve a better tradeoff between global exploration and local exploitation,but also greatly improve the optimization performance of HPCGA.It is concluded that HPCGA can elucidate the scientific basis for selecting the efficient numbers of subpopulations.

Providing a Therapeutic Scheduling for HIV Infected Individuals with Genetic Algorithms Using a Cellular Automata Model of HIV Infection in the Peripheral Blood Stream

The aim of this study is to develop two-dimensional cellular automata model of HIV infection that depicts the dynamics involved in the interactions between acquired immune system and HIV infection in the peripheral blood stream. The appropriate biological rules of cellular automata model have been extracted from expert knowledge and the model has been simulated with determined initial conditions. Obtained results have been validated through comparing with the accepted AIDS reference curve. The new rules and states were added to the proposed model to show the effects of applying combined antiretroviral therapy. Our results showed that by applying RTI and PI drugs with maximum drug effectiveness, comparing with cases in which no treatment was applied, the steady state concentrations of healthy (infected) CD4+T cells were increased (decreased) 53% (41%). Also, the use of cART with maximum drug effectiveness led to a 69% reduction in the steady state level of viral load. At this time, obtained results have been validated through comparing with available clinical data. Our results showed good agreement with both reference curve and the clinical data. In the second phase of this study, by applying genetic algorithms, a therapeutic schedule has been provided that its use, while maintaining the quality of the treatment, leads to a 47% reduction in both drug dosage and the side effects of antiretroviral drugs.

Modeling the Scheduling Problem in Cellular Manufacturing Systems Using Genetic Algorithm as an Efficient Meta-Heuristic Approach

This paper presents a new,bi-criteria mixed_integer programming model for scheduling cells and pieces within each cell in a manufacturing cellular system.The objective of this model is to minimize the makespan and intercell movements simultaneously,while considering sequence-dependent cell setup times.In the cellular manufacturing systems design and planning,three main steps must be considered,namely cell formation(i.e,piece families and machine grouping),inter and intra-cell layouts,and scheduling issue.Due to the fact that the cellular manufacturing systems problem is NP-Hard,a genetic algorithm as an efficient meta-heuristic method is proposed to solve such a hard problem.Finally,a number of test problems are solved to show the efficiency of the proposed genetic algorithm and the related computational results are compared with the results obtained by the use of an optimization tool.

Modeling of Trophospheric Ozone Concentrations Using Genetically Trained Multi-Level Cellular Neural Networks

Tropospheric ozone concentrations, which are an important air pollutant, are modeled by the use of an artificial intelligence structure. Data obtained from air pollution measurement stations in the city of Istanbul are utilized in constituting the model. A supervised algorithm for the evaluation of ozone concentration using a genetically trained multi-level cellular neural network （ML-CNN） is introduced, developed, and applied to real data. A genetic algorithm is used in the optimization of CNN templates. The model results and the actual measurement results are compared and statistically evaluated. It is observed that seasonal changes in ozone concentrations are reflected effectively by the concentrations estimated by the multilevel-CNN model structure, with a correlation value of 0.57 ascertained between actual and model results. It is shown that the multilevel-CNN modeling technique is as satisfactory as other modeling techniques in associating the data in a complex medium in air pollution applications.

PARALLEL GENETIC ALGORITHM ON PVM

In this paper we describe an implementation of some kinds of parallel genetic algorithms on the PVM,Parallel Virtual Machine, a portable parallel environment. We give details of a genetic algorithm running On many small subpopulations with an occasional identification and exchange of their useful information among subpopulations by means of message-passing functions of PVM. In this work, experiments were done to compare the parallel genetic algorithm and traditional sequential genetic algorithms.

基于CGA-BP神经网络的好氧堆肥曝气供氧量预测模型

为提高好氧堆肥曝气供氧量的曝气效率以及预测精度,该研究利用遗传算法(genetic algorithm,GA)对标准反向传播(back propagation,BP)神经网络的初始权值和阈值进行优化,再利用克隆选择算法(clonal genetic algorithm,CGA)优化遗传算法中的变异算子并复制算子,加快获取最优参数的速度,构建基于CGA-BP神经网络的曝气供氧量预测模型。为验证CGA-BP模型的有效性,与BP模型、GA-BP模型预测结果进行对比。试验结果表明:克隆遗传算法优化BP神经网络能加快获得最优解,效率相比BP模型和GA-BP模型分别提高了75.36%、51.30%;在曝气供氧量预测模型中,CGA-BP模型具有更准确的预测效果,预测精度为99.65%,而BP模型与GA-BP模型预测精度分别为96.99%、99.26%;CGA-BP模型评价指标的均方误差、平均绝对误差、平均绝对百分误差分别为0.0034、0.0389和0.3506,均小于BP神经网络和GA-BP神经网络模型评价指标的误差;利用CGA-BP好氧堆肥曝气供氧量预测模型对好氧堆肥发酵过程进行精准曝气,提高了3.22%的曝气控制效率。由此可知CGA-BP神经网络模型有更好的预测效果,可满足好氧堆肥在发酵过程中曝气供氧量的需求,提高曝气效率,为精准控制曝气提供更直接有效的方法。

点融合系统航班进场排序优化元胞自动机模型

针对点融合系统中航班调度问题,构建航班进场排序的二维元胞自动机模型,模拟先来先服务(first come first service, FCFS)和滑动窗口(sliding window, SDW)策略下的航班排序过程,对比不同策略下的终端区运行效率。实验结果表明:若都采用FCFS,使用中国民航航空器尾流重新分类标准(RECAT-CN)代替现行尾流间隔,进场航班流在点融合系统中的总运行时间减少了98 s,运行效率提升了4.3%;若都使用RECAT-CN间隔标准,采用SDW优化后的航班进场序列,较FCFS的总运行时间减少了193 s,运行效率提升了8.5%;点融合技术和RECAT-CN间隔标准可以实现终端区运行安全和效率的同步提升。

基于CGA和PSO的双种群混合算法

针对粒子群算法(PSO)收敛速度慢、求解精度不高以及易陷入局部最优的缺点,结合云遗传算法(CGA)和粒子群优化算法,提出一种新型的双种群混合算法(CGA-PSO)。将整个种群平均分成2个子群,分别采用云遗传算法和加入自调整惯性权值策略的粒子群优化算法完成进化。通过引入一种新型的信息交流机制:两子群子代间信息交流以及子代与父代间信息交流,共享最优个体,淘汰最劣个体,实现共同进化,适时对粒子群适应度较差的个体进行云变异操作,该操作是基于云模型的随机性和稳定性,利用全局最优位置和最劣位置实现对部分粒子位置的变异过程。对5个经典测试函数进行测试,并与CGA和PSO算法及其优化算法进行比较,结果表明,CGA-PSO算法具有较高的搜索效率、求解精度和较快的收敛速度,鲁棒性也较强。

基于遗传算法的团队CGA路径规划方法

基于遗传算法给出了一种团队CGA(Computer Generated Actors)全局路径规划方法,针对复杂环境和团队特点设计了不等长的路径编码和个体适应度评价方法.试验表明该方法可以为团队中每个成员规划出一条协调的、无障碍的路径,有效地解决复杂空间下团队CGA路径规划问题.

考虑子单元数量与起始位置的全覆盖路径规划

移动机器人的覆盖作业任务正朝着大面积和智能化方向发展,对全覆盖路径规划的覆盖效率与环境适应性提出迫切需求。为解决传统的牛耕单元分解法在复杂地图中适应性不足的问题,并提高覆盖效率,给出一种全覆盖路径规划方法。首先,在牛耕单元分解法的基础上,提出面积降序遍历与单调多边形判断的策略对子单元进行合并,减少约一半的子单元数量。最后,通过建立子单元起始位置与终止位置的映射关系,采用遗传算法优化子单元起始位置的选择和全局访问顺序。研究结果表明:1)文中算法在处理长宽为1300像素的地图时,能够在10 s内得到计算结果,并且相较于牛耕法、神经网络法和等高线法,计算时间随地图面积的增长率更小;2)相较于牛耕法、等高线法、神经网络法和能量最优法,文中算法的机器人总作业时间减少5.4%~47.0%,无效作业时间减少5.8%~29.2%;3)文中算法在1800张测试地图的平均覆盖率达到99.91%;4)统计检验进一步验证文中算法具有显著覆盖效率优势。

改进CGA在3D动漫造型设计中的应用

为自动生成新颖多样的3D动漫造型,提出一种改进的元胞遗传算法(CGA)。使用ACIS规则表达式对已有的3D动漫造型在3个方向上实施非均匀缩放变形,采用树结构编码生成长度和内容变化较大的规则表达式,通过人机交互的方式,利用专家知识确定个体适应度值。基于3D动漫造型创新系统ECTDS的实验结果表明,该算法可以生成一系列生动的创新造型。

改进的模糊交叉算子及其在CGA中的应用

基于标准化适应值信息,提出改进的模糊交叉算子,并应用到细胞状遗传算法(CGA)中。在具有局部搜索倾向的交叉操作中,该算子能使后代更偏向于适应值高的父体。在具有全局搜索倾向的交叉操作中,能使较差个体在更大范围内进行搜索,有效地引导CGA算法向全局最优解的方向收敛。仿真实验结果表明,基于改进模糊交叉算子的CGA算法性能更好。

Genetic algorithms for determining the parameters of cellular automata in urban simulation

This paper demonstrates that cellular automata(CA) can be a useful tool for analyzing the process of many geographical phenomena.There are many studies on using CA to simulate the evolution of cites.Urban dynamics is determined by many spatial variables.The contribution of each spatial variable to the simulation is quantified by its parameter or weight.Calibration procedures are usually required for obtaining a suitable set of parameters so that the realistic urban forms can be simulated.Each pa-rameter has a unique role in controlling urban morphology in the simulation.In this paper,these pa-rameters for urban simulation are determined by using empirical data.Genetic algorithms are used to search for the optimal combination of these parameters.There are spatial variations for urban dynam-ics in a large region.Distinct sets of parameters can be used to represent the unique features of urban dynamics for various subregions.A further experiment is to evaluate each set of parameters based on the theories of compact cities.It is considered that the better set of parameters can be identified ac-cording to the utility function in terms of compact development.This set of parameters can be cloned to other regions to improve overall urban morphology.The original parameters can be also modified to produce more compact urban forms for planning purposes.This approach can provide a useful ex-ploratory tool for testing various planning scenarios for urban development.

EVOLUTIONARY ALGORITHMS WITH PREFERENCE FOR MANUFACTURING CELLS FORMATION

Due to the combinatorial nature of cell formation problem and the characteristics of multi-objective and multi-constrain, a novel method of evolutionary algorithm with preference is proposed. The analytic hierarchy process （AHP） is adopted to determine scientifically the weights of the sub-objective functions. The satisfaction of constraints is considered as a new objective, the ratio of the population which doesn＇t satisfy all constraints is assigned as the weight of new objective. In addition, the self-adaptation of weights is applied in order to converge more easily towards the feasible domain. Therefore, both features multi-criteria and constrains are dealt with simultaneously. Finally, an example is selected from the literature to evaluate the performance of the proposed approach. The results validate the effectiveness of the proposed method in designing the manufacturing cells.

A New Parallel-by-Cell Approach to Undistorted DataCompression Based on Cellular Automatonand Genetic Algorithm

In this paper, a new parallel-by-cell approach to the undistorteddata compression based on cellular automaton and genetic algorithm is presented.The local compression rules in a cellular automaton are obtained by using a geneticevolutionary algorithm. The correctness of the hyper-parallel compression, the timecomplexity, and the relevant symbolic dynamic behaviour are discussed. In comparison with other traditional sequential or small-scale parallel methods for undistorteddata compression, the proposed approach shows much higher real-time performance,better suitability and feasibility for the systolic hardware implementation.

A novel chaotic optimization algorithm and its applications

This paper presents a chaos-genetic algorithm (CGA) that combines chaos and genetic algorithms. It can be used to avoid trapping in local optima profiting from chaos'randomness,ergodicity and regularity. Its property of global asymptotical convergence has been proved with Markov chains in this paper. CGA was applied to the optimization of complex benchmark functions and artificial neural network's (ANN) training. In solving the complex benchmark functions,CGA needs less iterative number than GA and other chaotic optimization algorithms and always finds the optima of these functions. In training ANN,CGA uses less iterative number and shows strong generalization. It is proved that CGA is an efficient and convenient chaotic optimization algorithm.

地铁车辆蜂窝式防爬器的结构设计及优化

为研究某型地铁车辆蜂窝式防爬器的吸能特性,根据轨道车辆耐撞性标准,对其吸能区域的结构进行合理设计,进而研究了不同薄壁壳厚度和蜂窝厚度下蜂窝式防爬器的吸能特性。利用四次多项式响应面代理模型拟合出其压缩力效率,并运用多岛遗传算法对其压缩力效率最大值进行寻优。结果表明:多级蜂窝式防爬器的比吸能和压缩力效率都明显优于相同质量下的单级蜂窝式防爬器和圆管式防爬器;薄壁壳壁厚对多级蜂窝式防爬器的撞击力影响较铝蜂窝壁厚更为显著;通过使用四次多项式响应面法和多岛遗传算法在设计空间中寻找到其最优的壁厚组合,压缩力效率比优化前提高了6.03%,相较圆管式防爬器提高了60.96%;该防爬器在压缩力效率和比吸能方面具有明显优势,应用于地铁车辆的吸能防爬环节将发挥其重要的作用。

一种针对QCA电路自动布局布线的混合策略研究

量子元胞自动机(Quantum Cellular Automata,QCA)电路的自动布局布线是在相关约束条件下自动放置电路单元、自动形成连线,实现门级或元胞级电路的设计过程,是QCA电路设计大型化、复杂化和系统化的必要工具.布局布线算法设计过程中最大的难题是如何解决“时钟同步”,随着二维时钟方案提出,该问题的解决方案变得更加策略化,但仍存在诸多缺陷,如成功率低,布局面积较大等.本文将二维时钟方案的布局布线问题抽象成组合优化模型,提出了一种基于遗传算法GA(Genetic Algorithm)和改进A^(*)算法的混合策略.两种算法相互配合搭建可能的电路布局,并通过精心设计的适应度函数,搜索满足时钟同步的个体,最终实现从硬件电路到二维时钟方案上的门级布局.实验结果表明,本算法在目前被广泛应用的二维时钟方案USE(Universal,Scalable and Efficient)上的布局成功率接近100%.相较当前世界上最先进的两个QCA布局布线工具fiction和Ropper,本算法可适用电路规模更大(逻辑门数量大于10),在成功率和生成布局面积上都有大幅度的优化.

Modeling the spread of spatio-temporal phenomena through the incorporation of ANFIS and genetically controlled cellular automata: a case study on forest fire

Virtual representation and simulation of spatio-temporal phenomena is a promising goal for the production of an advanced digital earth.Spread modeling,which is one of the most helpful analyses in the geographic information system(GIS),plays a prominent role in meeting this objective.This study proposes a new model that considers both aspects of static and dynamic behaviors of spreadable spatio-temporal in cellular automata(CA)modeling.Therefore,artificial intelligence tools such as adaptive neuro-fuzzy inference system(ANFIS)and genetic algorithm(GA)were used in accordance with the objectives of knowledge discovery and optimization.Significant conditions in updating states are considered so traditional CA transition rules can be accompanied with the impact of fuzzy discovered knowledge and the solution of spread optimization.We focused on the estimation of forest fire growth as an important case study for decision makers.A two-dimensional cellular representation of the combustion of heterogeneous fuel types and density on non-flat terrain were successfully linked with dynamic wind and slope impact.The validation of the simulation on experimental data indicated a relatively realistic head-fire shape.Further investigations showed that the results obtained using the dynamic controlling with GA in the absence of static modeling with ANFIS were unacceptable.