A genetic algorithm approach to multiobjective land use planning

This paper describes a class of spatial planning problems in which different land uses have to be allocated across a geographical region, subject to a variety of constraints and conflicting management objectives. A goal programming/reference point approach to the problem is formulated, which leads however to a difficult nonlinear combinatorial optimization problem. A special purpose genetic algorithm is developed for the solution of this problem, and is extensively tested numerically. The model and algorithm is then applied to a specific land use planning problem in The Netherlands. The ultimate goal is to integrate the algorithm into a complete land use planning decision support system.     

A new vertical fragmentation algorithm based on ant collective behavior in distributed database systems

Considering the existing massive volumes of data processed nowadays and the distributed nature of many organizations, there is no doubt how vital the need is for distributed database systems. In such systems, the response time to a transaction or a query is highly affected by the distribution design of the database system, particularly its methods for fragmentation, replication, and allocation data. According to the relevant literature, from the two approaches to fragmentation, namely horizontal and vertical fragmentation, the latter requires the use of heuristic methods due to it being NP-Hard. Currently, there are a number of different methods of providing vertical fragmentation, which normally introduce a relatively high computational complexity or do not yield optimal results, particularly for large-scale problems. In this paper, because of their distributed and scalable nature, we apply swarm intelligence algorithms to present an algorithm for finding a solution to vertical fragmentation problem, which is optimal in most cases. In our proposed algorithm, the relations are tried to be fragmented in such a way so as not only to make transaction processing at each site as much localized as possible, but also to reduce the costs of operations. Moreover, we report on the experimental results of comparing our algorithm with several other similar algorithms to show that ours outperforms the other algorithms and is able to generate a better solution in terms of the optimality of results and computational complexity.     

Evaluation of different initial solution algorithms to be used in the heuristics optimization to solve the energy resource scheduling in smart grids

Over the last years, an increasing number of distributed resources have been connected to the power system due to the ambitious environmental targets, which resulted into a more complex operation of the power system. In the future, an even larger number of resources is expected to be coupled which will turn the day-ahead optimal resource scheduling problem into an even more difficult optimization problem. Under these circumstances, metaheuristics can be used to address this optimization problem. An adequate algorithm for generating a good initial solution can improve the metaheuristic’s performance of finding a final solution near to the optimal than using a random initial solution. This paper proposes two initial solution algorithms to be used by a metaheuristic technique (simulated annealing). These algorithms are tested and evaluated with other published algorithms that obtain initial solution. The proposed algorithms have been developed as modules to be more flexible their use by other metaheuristics than just simulated annealing. The simulated annealing with different initial solution algorithms has been tested in a 37-bus distribution network with distributed resources, especially electric vehicles. The proposed algorithms proved to present results very close to the optimal with a small difference between 0.1%. A deterministic technique is used as comparison and it took around 26 h to obtain the optimal one. On the other hand, the simulated annealing was able of obtaining results around 1 min.     

遗传算法在土地利用优化中的应用

城市土地利用优化是从社会的长远与整体利益的角度,来规范一定时段内城市土地利用的结构、布局和方式,是一个典型的多目标优化问题.本文利用遗传算法的全局优化搜索能力,构建了一个城市土地利用的优化模型.该模型采用与土地利用现状图相对应的二维矩阵编码,利用层次分析法构建了顾及土地功能协调性、土地比例协调性、人口、交通4个方面的多目标适应度函数.应用该模型对某城市的城市土地利用空间结构进行了优化配置.结果表明,该模型能够反映城市土地利用的客观规律,优化后的方案能很好地符合城市规划上的各种需要.     

Quasi-random initial population for genetic algorithms

The selection of the initial population in a population-based heuristic optimizationmethod is important, since it affects the search for several iterations and often has an influence on the final solution. If no a priori information about the optima is available, the initial population is often selected randomly using pseudorandom numbers. Usually, however, it is more important that the points are as evenly distributed as possible than that they imitate random points. In this paper, we study the use of quasi-random sequences in the initial population of a genetic algorithm. Sample points in a quasi-random sequence are designed to have good distribution properties. Here a modified genetic algorithm using quasi-random sequences in the initial population is tested by solving a large number of continuous benchmark problems from the literature. The numerical results of two implementations of genetic algorithms using different quasi-random sequences are compared to those of a traditional implementation using pseudorandom numbers. The results obtained are promising.     

Convergence Acceleration Operator for Multiobjective Optimization

A convergence acceleration operator (CAO) is described which enhances the search capability and the speed of convergence of the host multiobjective optimization algorithm. The operator acts directly in the objective space to suggest improvements to solutions obtained by a multiobjective evolutionary algorithm (MOEA). The suggested improved objective vectors are then mapped into the decision variable space and tested. This method improves upon prior work in a number of important respects, such as mapping technique and solution improvement. Further, the paper discusses implications for many-objective problems and studies the impact of the use of the CAO as the number of objectives increases. The CAO is incorporated with two leading MOEAs, the non-dominated sorting genetic algorithm and the strength Pareto evolutionary algorithm and tested. Results show that the hybridized algorithms consistently improve the speed of convergence of the original algorithm while maintaining the desired distribution of solutions. It is shown that the operator is a transferable component that can be hybridized with any MOEA.      

High performance genetic algorithm for land use planning

This study uses genetic algorithms to formulate and develop land use plans. The restrictions to be imposed and the variables to be optimized are selected based on current local and national legal rules and experts’ criteria. Other considerations can easily be incorporated in this approach. Two optimization criteria are applied: land suitability and the shape-regularity of the resulting land use patches. We consider the existing plots as the minimum units for land use allocation. As the number of affected plots can be large, the algorithm execution time is potentially high. The work thus focuses on implementing and analyzing different parallel paradigms: multi-core parallelism, cluster parallelism and the combination of both. Some tests were performed that show the suitability of genetic algorithms to land use planning problems.     

A new multiple seeds based genetic algorithm for discovering a set of interesting Boolean association rules

Association rule mining algorithms mostly use a randomly generated single seed to initialize a population without paying attention to the effectiveness of that population in evolutionary learning. Recently, research has shown significant impact of the initial population on the production of good solutions over several generations of a genetic algorithm. Single seed based genetic algorithms suffer from the following major challenges (1) solutions of a genetic algorithm are varied, since different seeds generate different initial population, (2) difficulty in defining a good seed for a specific application. To avoid these problems, in this paper we propose the MSGA, a new multiple seeds based genetic algorithm which generates multiple seeds from different domains of a solution space to discover high quality rules from a large data set. This scheme introduces m-domain model and m-seeds selection process through which the whole solution space is subdivided into m- number of same size domains, selecting a seed from each domain. Use of these seeds enables this method to generate an effective initial population for evolutionary learning of the fitness value of each rule. As a result, strong searching efficiency is obtained at the beginning of the evolution, achieving fast convergence. The MSGA is tested with different mutation and crossover operators for mining interesting Boolean association rules from four real world data sets. The results are compared to different single seeds based genetic algorithms under the same conditions.     

A genetic algorithm for the multiple destination routing problems

The multiple destination routing (MDR) problem can be formulated as finding a minimal cost tree which contains designated source and multiple destination nodes so that certain constraints in a given communication network are satisfied. This is a typical NP-hard problem, and therefore only heuristic algorithms are of practical value. As a first step, a new genetic algorithm is developed to solve the MDR problems without constraints. It is based on the transformation of the underlying network of an MDR problem into its distance complete form, a natural chromosome representation of a minimal spanning tree (an individual), and a completely new computation of the fitness of individual. Compared with the known genetic algorithms and heuristic algorithms for the same problem, the proposed algorithm has several advantages. First, it guarantees convergence to an optimal solution with probability one. Second, not only are the resultant solutions all feasible, the solution quality is also much higher than that obtained by the other methods (indeed, in almost every case in our simulations, the algorithm can find the optimal solution of the problem). Third, the algorithm is of low computational complexity, and this can be decreased dramatically as the number of destination nodes in the problem increases. The simulation studies for the sparse and dense networks all demonstrate that the proposed algorithm is highly robust and very efficient in the sense of yielding high-quality solutions     

基于改进模拟植物生长算法的配电网重构

针对模拟植物生长算法所存在的需遍历搜索区域进行寻优导致计算量太大的问题。将支路交换算法中所用的启发式交换规则与之相结合。提出一种用于配电网重构的改进模拟植物生长算法。所提方法的主要优点,是在保留模拟植物生长算法所具备的全局寻优能力的同时,大大减少每一步计算中所产生的生长点集的数量,因而减少相应的潮流计算、目标函数值计算及形态素浓度计算的次数即计算量．对IEEE33节点系统的计算结果,验证所提方法的有效性。     

遥感用于土地利用变化动态监测中的若干问题探讨

利用遥感与地理信息系统技术进行土地资源调查和动态变化监测已为人们所共识。由于土地 利用与土地覆盖的复杂性,利用遥感技术进行土地利用变化动态监测时,遇到了许多具体问题。从 应用的角度出发,重点在土地利用与土地覆盖的关系、影像的选择与处理、动态监测方法的选定与 综合及其它多方面知识的参与等几个方面进行了探讨。这些问题的解决,将会在很大程度上提高土 地利用变化监测的精度。     

A modified genetic algorithm with fuzzy roulette wheel selection for job-shop scheduling problems

The job-shop scheduling problem is one of the most difficult production planning problems. Since it is in the NP-hard class, a recent trend in solving the job-shop scheduling problem is shifting towards the use of heuristic and metaheuristic algorithms. This paper proposes a novel metaheuristic algorithm, which is a modification of the genetic algorithm. This proposed algorithm introduces two new concepts to the standard genetic algorithm: (1) fuzzy roulette wheel selection and (2) the mutation operation with tabu list. The proposed algorithm has been evaluated and compared with several state-of-the-art algorithms in the literature. The experimental results on 53 JSSPs show that the proposed algorithm is very effective in solving the combinatorial optimization problems. It outperforms all state-of-the-art algorithms on all benchmark problems in terms of the ability to achieve the optimal solution and the computational time.     

A parallel evolutionary algorithm to optimize dynamic data types in embedded systems

New multimedia embedded applications are increasingly dynamic, and rely on dynamically-allocated data types (DDTs) to store their data. The optimization of DDTs for each target embedded system is a time-consuming process due to the large searching space of possible DDTs implementations. That implies the minimization of embedded design variables (memory accesses, power consumption and memory usage). Up to know, some very effective heuristic algorithms have been developed in order to solve this problem, but it is unknown how good the selected DDTs are since the problem is NP-complete and cannot be fully explored. In these cases the use of parallel processing can be very useful because it allows not only to explore more solutions spending the same time, but also to implement new algorithms. This paper describes several parallel evolutionary algorithms for DDTs optimization in Embedded Systems, where parallelism improves the solutions found by the corresponding sequential algorithm, which indeed is quite effective compared with other previously proposed procedures. Experimental results show how a novel parallel multi-objective genetic algorithm, which combines NSGA-II and SPEA2, allows designers to reach a larger number of solutions than previous approximations.     

一种并行多目标遗传邻域搜索算法

现有的多目标遗传算法在解决大规模多目标生产调度问题时虽然有效,但往往非常耗时,难以应用于实际.为了提高求解效率,提出了一种并行多目标遗传邻域搜索算法来求解Pareto边界.该算法将多目标遗传算法的进化方向划分为若干范围,然后同时对每个进化方向的范围使用多目标遗传邻域搜索算法,并行地搜索各方向范围内的Pareto边界;在各进化方向范围内进化的子种群会定期交流各自进化成果.多目标遗传邻域搜索算法的并行化在不增加求解时间的前提下,提高了求解精度,加快了算法的收敛速度.仿真实验结果验证了算法的可行性与有效性.     

A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops

Obtaining an optimal solution for a permutation flowshop scheduling problem with the total flowtime criterion in a reasonable computational timeframe using traditional approaches and optimization tools has been a challenge. This paper presents a discrete artificial bee colony algorithm hybridized with a variant of iterated greedy algorithms to find the permutation that gives the smallest total flowtime. Iterated greedy algorithms are comprised of local search procedures based on insertion and swap neighborhood structures. In the same context, we also consider a discrete differential evolution algorithm from our previous work. The performance of the proposed algorithms is tested on the well-known benchmark suite of Taillard. The highly effective performance of the discrete artificial bee colony and hybrid differential evolution algorithms is compared against the best performing algorithms from the existing literature in terms of both solution quality and CPU times. Ultimately, 44 out of the 90 best known solutions provided very recently by the best performing estimation of distribution and genetic local search algorithms are further improved by the proposed algorithms with short-term searches. The solutions known to be the best to date are reported for the benchmark suite of Taillard with long-term searches, as well.     

A tribe competition-based genetic algorithm for feature selection in pattern classification

Feature selection has always been a critical step in pattern recognition, in which evolutionary algorithms, such as the genetic algorithm (GA), are most commonly used. However, the individual encoding scheme used in various GAs would either pose a bias on the solution or require a pre-specified number of features, and hence may lead to less accurate results. In this paper, a tribe competition-based genetic algorithm (TCbGA) is proposed for feature selection in pattern classification. The population of individuals is divided into multiple tribes, and the initialization and evolutionary operations are modified to ensure that the number of selected features in each tribe follows a Gaussian distribution. Thus each tribe focuses on exploring a specific part of the solution space. Meanwhile, tribe competition is introduced to the evolution process, which allows the winning tribes, which produce better individuals, to enlarge their sizes, i.e. having more individuals to search their parts of the solution space. This algorithm, therefore, avoids the bias on solutions and requirement of a pre-specified number of features. We have evaluated our algorithm against several state-of-the-art feature selection approaches on 20 benchmark datasets. Our results suggest that the proposed TCbGA algorithm can identify the optimal feature subset more effectively and produce more accurate pattern classification.     

MCEDA: A novel many-objective optimization approach based on model and clustering

To solve many-objective optimization problems (MaOPs) by evolutionary algorithms (EAs), the maintenance of convergence and diversity is essential and difficult. Improved multi-objective optimization evolutionary algorithms (MOEAs), usually based on the genetic algorithm (GA), have been applied to MaOPs, which use the crossover and mutation operators of GAs to generate new solutions. In this paper, a new approach, based on decomposition and the MOEA/D framework, is proposed: model and clustering based estimation of distribution algorithm (MCEDA). MOEA/D means the multi-objective evolutionary algorithm based on decomposition. The proposed MCEDA is a new estimation of distribution algorithm (EDA) framework, which is intended to extend the application of estimation of distribution algorithm to MaOPs. MCEDA was implemented by two similar algorithm, MCEDA/B (based on bits model) and MCEDA/RM (based on regular model) to deal with MaOPs. In MCEDA, the problem is decomposed into several subproblems. For each subproblem, clustering algorithm is applied to divide the population into several subgroups. On each subgroup, an estimation model is created to generate the new population. In this work, two kinds of models are adopted, the new proposed bits model and the regular model used in RM-MEDA (a regularity model based multi-objective estimation of distribution algorithm). The non-dominated selection operator is applied to improve convergence. The proposed algorithms have been tested on the benchmark test suite for evolutionary algorithms (DTLZ). The comparison with several state-of-the-art algorithms indicates that the proposed MCEDA is a competitive and promising approach.     

遗传算法与蚂蚁算法的融合

遗传算法具有快速随机的全局搜索能力，但对于系统中的反馈信息利用却无能为力，当求解到一定范围时往往做大量无为的冗余迭代，求精确解效率低．蚂蚁算法是通过信息素的累积和更新收敛于最优路径上，具有分布式并行全局搜索能力，但初期信息素匮乏，求解速度慢，算法是将遗传算法与蚂蚁算法融合，采用遗传算法生成信息素分布，利用蚂蚁算法求精确解，优势互补，仿真表明取得了非常好的效果。     

A novel two-stage hybrid swarm intelligence optimization algorithm and application

This paper presents a novel two-stage hybrid swarm intelligence optimization algorithm called GA–PSO–ACO algorithm that combines the evolution ideas of the genetic algorithms, particle swarm optimization and ant colony optimization based on the compensation for solving the traveling salesman problem. In the proposed hybrid algorithm, the whole process is divided into two stages. In the first stage, we make use of the randomicity, rapidity and wholeness of the genetic algorithms and particle swarm optimization to obtain a series of sub-optimal solutions (rough searching) to adjust the initial allocation of pheromone in the ACO. In the second stage, we make use of these advantages of the parallel, positive feedback and high accuracy of solution to implement solving of whole problem (detailed searching). To verify the effectiveness and efficiency of the proposed hybrid algorithm, various scale benchmark problems from TSPLIB are tested to demonstrate the potential of the proposed two-stage hybrid swarm intelligence optimization algorithm. The simulation examples demonstrate that the GA–PSO–ACO algorithm can greatly improve the computing efficiency for solving the TSP and outperforms the Tabu Search, genetic algorithms, particle swarm optimization, ant colony optimization, PS–ACO and other methods in solution quality. And the experimental results demonstrate that convergence is faster and better when the scale of TSP increases.     

最短路由问题的改进单亲进化遗传算法

基于信息素动态更新的蚁群算法(DACO)求解大规模最短路由问题收敛时间过长,单亲进化遗传算法(PEGA)在产生初始种群、选择父体及基因换位等操作中存在随机性太大的问题,论章将这两种算法相结合,提出了基于改进蚁群算法的单亲进化遗传算法(DACO-PEGA),该算法通过控制蚁群周游次数,求得满意可行解或次优解,再将已得路由作为初始种群进行优化改良,求得最短路由。实验结果表明,该算法应用于求解最短路由问题行之有效.