Generative methods and the design process: A design tool for conceptual settlement planning

This paper implores the possible intervention of computers in the generative (concept) stage of settlement planning. The objective was to capture the complexity and character of naturally grown fishing settlements through simple rules and incorporate them in the process of design. A design tool was developed for this purpose. This design tool used a generative evolutionary design technique, which is based on multidisciplinary methods. Facets of designing addressed in this research are:

• •allocation of each design element's space and geometry,
• •defining the rules, constraints and relationships governing the elements of design,
• •the purposeful search for better alternative solutions,
• •quantitative evaluation of the solution based on spatial, comfort, complexity criterions to ensure the needed complexity, usability in the solutions.

Generative design methods such as geometric optimization, shape grammars and genetic algorithms have been combined for achieving the above purposes.The allocation of space has been achieved by geometric optimization techniques, which allocate spaces by proliferation of a simple shape unit. This research conducts an analysis of various naturally grown fishing settlements and identifies the features that would be essential to recreate such an environment. Features such as the essential elements, their relationships, hierarchy, and order in the settlement pattern, which resulted due to the occupational and cultural demands of the fisher folk, are analysed. The random but ordered growth of the settlement is captured as rules and relations. These rules propel and guide the whole process of design generation.These rules and certain constraints, restrictions control the random arrangement of the shape units. This research limits itself to conducting exhaustive search in the prescribed solution search space defined a priori by the rules and relationships. This search within a bounded space can be compared to the purposeful, constrained decision making process involved in designing.The generated solutions use the evolutionary concept of genetic algorithms to deduce solutions within the predefined design solution search space. Simple evolutionary concepts such as reproduction, crossover and mutation aid this search process. These concepts transform by swapping/interchanging the genetic properties (the constituent data/material making up the solution) of two generated solutions to produce alternate solutions. Thus the genetic algorithm finds a series of new solutions. With such a tool in hand various possibilities of design solutions could be analysed and compared. A thorough search of possible solutions ensures a deeper probe essential for a good design.The spatial quality, comfort quality of the solutions are compared and graded (fitness value) against the standard stipulations. These parameters look at the solution in the context of the whole and not as parts and most of these parameters could be improved only at the expense of another. The tool is able to produce multiple equally good solutions to the same problem, possibly with one candidate solution optimizing one parameter and another candidate optimizing a different one. The final choice of the suitable solution is made based on the user's preferences and objectives.The tool is tested for an existing fishing settlement. This was done to check for its credibility and to see if better alternatives evolved. The existing settlement is analysed based on the evaluation parameters used in the tool and compared with the generated solutions. The results of the tool has proved that simple rules when applied recursively within constraints would provide solutions that are unpredictable and also would resonate the qualities of the knowledge from which the rules were distilled from. The complex whole generated has often exhibited emergent properties and thus opens up new avenues of thinking.     

基于改进遗传算法的资源优化配置研究

当前在解决资源优化配置问题时往往使用贪婪算法、遗传算法等.但贪婪算法只能选择一个最优度量标准,所以只能获得度量意义下的最优解而不是该问题的最优解,而如果直接使用遗传算法又存在搜索空间过大、耗时过长的问题.提出了一种新的算法.先基于贪婪算法获得问题的初始解空间,然后对初始解空间进行冲突检测与消解,最后运用改进的遗传算法进行优化获得最优方案.测试算例表明大大缩小了遗传算法的搜索空间,在保证获得最优解的条件下加快了收敛速度并有效防止了种群的退化.提出的算法在突发事务的处理方面具有一定的意义.     

遗传算法求解VRP问题

在分析了许多求解固定车辆路径问题的优化算法后，提出了一种新的求解固定车辆路径问题的遗传算法。该算法的核心在于构建一种新的染色体编码，并且将“Inver-0ver”遗传操作算子与禁忌搜索算法结合起来，利用种群的信息引导种群的进化。引入动态非法检测来淘汰不合法个体，扩展了解空间并加快了搜索速度。经过大量的实例测试，该遗传算法增强了群体演化的质量，提高了算法收敛速度，能够找到比较好的近似最优解。     

An evolutionary algorithm with guided mutation for the maximum clique problem

Estimation of distribution algorithms sample new solutions (offspring) from a probability model which characterizes the distribution of promising solutions in the search space at each generation. The location information of solutions found so far (i.e., the actual positions of these solutions in the search space) is not directly used for generating offspring in most existing estimation of distribution algorithms. This paper introduces a new operator, called guided mutation. Guided mutation generates offspring through combination of global statistical information and the location information of solutions found so far. An evolutionary algorithm with guided mutation (EA/G) for the maximum clique problem is proposed in this paper. Besides guided mutation, EA/G adopts a strategy for searching different search areas in different search phases. Marchiori's heuristic is applied to each new solution to produce a maximal clique in EA/G. Experimental results show that EA/G outperforms the heuristic genetic algorithm of Marchiori (the best evolutionary algorithm reported so far) and a MIMIC algorithm on DIMACS benchmark graphs.     

一种基于分散搜索的多星测控调度遗传算法

多星测控调度是一个具有大搜索空间的多峰问题。针对简单遗传算法求解易陷入局部最优和不稳定的缺陷,借鉴分散搜索多样化采样、局部寻优的特点,提出一种基于分散搜索的混合遗传算法,在全局的随机搜索中嵌入全局的定向搜索。在描述问题的基础上,提出可进行细粒度搜索的可行解表示方式,构建算法的整体流程,并设计由输入参数控制的多样化初始集产生方法、基于质量和多样性原则的参考集生成和更新方法、吸取被组合个体优良成份的解组合方法及基于启发式局部搜索的解提高方法等算法要素。仿真表明新算法在求解质量上比简单遗传算法有明显提高。     

Nonlinear inversion of potential-field data using a hybrid-encoding genetic algorithm

Using a genetic algorithm to solve an inverse problem of complex nonlinear geophysical equations is advantageous because it does not require computer gradients of models or “good” initial models. The multi-point search of a genetic algorithm makes it easier to find the globally optimal solution while avoiding falling into a local extremum. As is the case in other optimization approaches, the search efficiency for a genetic algorithm is vital in finding desired solutions successfully in a multi-dimensional model space. A binary-encoding genetic algorithm is hardly ever used to resolve an optimization problem such as a simple geophysical inversion with only three unknowns. The encoding mechanism, genetic operators, and population size of the genetic algorithm greatly affect search processes in the evolution. It is clear that improved operators and proper population size promote the convergence. Nevertheless, not all genetic operations perform perfectly while searching under either a uniform binary or a decimal encoding system. With the binary encoding mechanism, the crossover scheme may produce more new individuals than with the decimal encoding. On the other hand, the mutation scheme in a decimal encoding system will create new genes larger in scope than those in the binary encoding. This paper discusses approaches of exploiting the search potential of genetic operations in the two encoding systems and presents an approach with a hybrid-encoding mechanism, multi-point crossover, and dynamic population size for geophysical inversion. We present a method that is based on the routine in which the mutation operation is conducted in the decimal code and multi-point crossover operation in the binary code. The mix-encoding algorithm is called the hybrid-encoding genetic algorithm (HEGA). HEGA provides better genes with a higher probability by a mutation operator and improves genetic algorithms in resolving complicated geophysical inverse problems. Another significant result is that final solution is determined by the average model derived from multiple trials instead of one computation due to the randomness in a genetic algorithm procedure. These advantages were demonstrated by synthetic and real-world examples of inversion of potential-field data.     

Mountain railway alignment optimization using stepwise & hybrid particle swarm optimization incorporating genetic operators

Optimizing railway alignments is a quite complex and time-consuming engineering problem. The huge continuous search space, complex constraints, implicit objective function and infinite potential alternatives of this problem pose many challenges. Especially in mountainous regions, finding a near-optimal alignment for extremely complex terrain and constraints is a most arduous task, which cannot be solved satisfactorily with most existing methods. In this study, a stepwise & hybrid particle swarm-genetic algorithm is developed for railway alignment optimization in mountainous regions. It is a continuous search method suitable for railway alignment design. A stepwise horizontal–vertical–integral approach which defines the horizontal and vertical alignments as two kinds of particles, is proposed to solve the three-dimensional railway alignment optimization problem. To enhance the initial diversity and momentum, butterfly-shaped areas are preset on a path generated with a bidirectional distance transform for initializing horizontal particles. For the solution method, specific genetic operators, including roulette wheel selection, four crossovers and two mutations are integrated into the stepwise particle swarm method to address parameter-dependent performance and avoid premature convergence. In addition, a cubic polynomial weight update strategy is employed for thoroughly searching the problem space. This synthesis method has been applied to a real-world case in a very mountainous region. The detailed data analyses demonstrate that it can offer more promising solutions compared with alternatives designed by experienced designers and those generated with a genetic algorithm or non-stepwise particle swarm algorithm.     

一种基于进化泛函网络的建模与函数逼近方法

提出了一种进化泛函网络的建模与函数逼近方法,该方法把泛函网络建模过程转变为结构和泛函参数的优化搜索过程,利用遗传规划设计泛函网络神经元函数,对网络结构和参数共存且相互影响的复杂解空间进行全局最优搜索,实现泛函网络结构和参数的共同学习,并用混合基函数实现目标函数的逼近,改变了人们通常用同类型基函数来实现目标函数逼近的方式.数值仿真结果表明,提出的网络建模与逼近方法具有较高的逼近精度.     

Searching the Solution Space in Constructive Geometric Constraint Solving with Genetic Algorithms

Geometric problems defined by constraints have an exponential number of solution instances in the number of geometric elements involved. Generally, the user is only interested in one instance such that besides fulfilling the geometric constraints, exhibits some additional properties. Selecting a solution instance amounts to selecting a given root every time the geometric constraint solver needs to compute the zeros of a multi valuated function. The problem of selecting a given root is known as the Root Identification Problem.In this paper we present a new technique to solve the root identification problem. The technique is based on an automatic search in the space of solutions performed by a genetic algorithm. The user specifies the solution of interest by defining a set of additional constraints on the geometric elements which drive the search of the genetic algorithm. The method is extended with a sequential niche technique to compute multiple solutions. A number of case studies illustrate the performance of the method.     

复杂参数产品形态设计中的解空间降维方法

针对产品形态设计中评价标准的模糊性问题,探索了智能化设计方法中的操作性技术.基于产品的形态编码,采用参数权重集中曲线的噪声度自动评测方式对解空间进行降维处理,并对产品形态编码分级.在降维后的系列解空间中使用交互式遗传算法搜索最优方案,并逐级完成形态的细化设计.文中方法从用户交互选择信息中提取出各参数对产品形态的重要性等级,作为细化设计过程的依据.求解过程全部基于解码的形态方案进行,为设计师的工作提供了直观的界面.     

一种改进的变焦遗传算法

提出一种新的变焦遗传算法,在保持串长不变的条件下,大幅度缩小搜索区间,明显提高了遗传算法的收敛速度和解的精度.本文提出的方法对大范围、高精度情况尤其适合.仿真结果说明了算法的有效 性.􀁽     

Multi-objective genetic local search algorithm using Kohonen’s neural map

Genetic Algorithms (GAs) are population based global search methods that can escape from local optima traps and find the global optima regions. However, near the optimum set their intensification process is often inaccurate. This is because the search strategy of GAs is completely probabilistic. With a random search near the optimum sets, there is a small probability to improve current solution. Another drawback of the GAs is genetic drift. The GAs search process is a black box process and no one knows that which region is being searched by the algorithm and it is possible that GAs search only a small region in the feasible space. On the other hand, GAs usually do not use the existing information about the optimality regions in past iterations.In this paper, a new method called SOM-Based Multi-Objective GA (SBMOGA) is proposed to improve the genetic diversity. In SBMOGA, a grid of neurons use the concept of learning rule of Self-Organizing Map (SOM) supporting by Variable Neighborhood Search (VNS) learn from genetic algorithm improving both local and global search. SOM is a neural network which is capable of learning and can improve the efficiency of data processing algorithms. The VNS algorithm is developed to enhance the local search efficiency in the Evolutionary Algorithms (EAs). The SOM uses a multi-objective learning rule based-on Pareto dominance to train its neurons. The neurons gradually move toward better fitness areas in some trajectories in feasible space. The knowledge of optimum front in past generations is saved in form of trajectories. The final state of the neurons determines a set of new solutions that can be regarded as the probability density distribution function of the high fitness areas in the multi-objective space. The new set of solutions potentially can improve the GAs overall efficiency. In the last section of this paper, the applicability of the proposed algorithm is examined in developing optimal policies for a real world multi-objective multi-reservoir system which is a non-linear, non-convex, multi-objective optimization problem.     

基于遗传算法模式匹配的机器人实时视觉伺服

对于机器人手臂来讲 ,对工作环境的识别是完成一个智能任务的最重要的问题之一 .因为这种智能可以使它工作在一个变化的环境中 .本文提出了一种新的机器人手臂的控制策略 ,可以利用视觉信息来指导机器人的手臂在它的工作空间中捡起一个已知形状但任意位置和方向的物体 .在对物体的搜索过程中 ,利用基于视觉闭环的视觉伺服来完成对机器人手臂的运动控制 .本系统利用遗传算法 (Genetic Algorithm ,GA)和模式匹配技术完成对搜索空间的搜索并获得了良好的结果 .本文完成了对带有两连杆手臂的视觉伺服系统的仿真 ,仿真结果证明了算法的有效性     

Minimizing a nonlinear function under a fuzzy max-t-norm relational equation constraint

This work studies a nonlinear optimization problem subject to fuzzy relational equations with max-t-norm composition. Since the feasible domain of fuzzy relational equations with more than one minimal solution is non-convex, traditional nonlinear programming methods usually cannot solve them efficiently. This work proposes a genetic algorithm to solve this problem. This algorithm first locates the feasible domain through the maximum solution and the minimal solutions of the fuzzy relational equations, to significantly reduce the search space. The algorithm then executes all genetic operations inside this feasible domain, and thus avoids the need to check the feasibility of each solution generated. Moreover, it uses a local search operation to fine-tune each mutated solution. Experimental results indicate that the proposed algorithm can accelerate the searching speed and find the optimal solution.     

Modified fuzzy ants clustering approach

Being trapped in local optima within clustering search space currently is nontrivial difficulty. In order to relieve such a difficulty, even using genetic algorithm to optimize the initial clusters for fuzzy c-means is still unsatisfied. Since genetic algorithm intensifies only the current best solution, it will easily gets trapped in local minima. The ant colony system, dissimilarly to genetic algorithm, recognizes that the solutions near the best solution are also good ones and they bring about smoothness of solution. This paper proposes a modified fuzzy ant clustering. Such a presented method is a combination of genetic algorithm, ant colony system and fuzzy c-means. It is employed in creating fuzzy color histogram in image retrieval application. The performance measurement relates to the percentages of accuracy of image retrieval. Experimental results show that the proposed approach yields the best results among others with respect to sensitivity and robustness on dealing with lighting intensity changes, quantization errors, also changes in number of images and in size of color space, even the certain-range variation of a particular parameter of clustering.     

周期变异概率的免疫克隆算法

在传统免疫克隆算法的基础上提出了一种新的基于周期变异概率的免疫克隆算法,该算法进一步提高了收敛速度,有效地克服了早熟现象,很好地解决了类似高维函数优化等复杂问题.通过对比计算实验表明:种群的初始分布对该算法的性能影响很小,且对待寻优空间的全局搜索能力和局部搜索能力以及算法的稳定性与计算速率都要强于简单免疫克隆算法和自适应遗传算法等优化算法.     

应用于分类EST序列拼接的并行遗传算法

利用EST（Expresscd Sequence Tag)序列数据发现新基因，是当前国际上基因组研究的热点，但程序设计十分复杂。计算量非常巨大。而遗传算法是一种能在复杂而庞大的搜索空间中利用问题的固有知识来缩小搜索范围，避免组合爆炸，从而得到最优解或准最优解的通用搜索算法。该文结合核酸序列的特征，提出了一种改进的并行遗传算法，应用于EST序列拼接的组合优化。     

Truss optimization on shape and sizing with frequency constraints based on parallel genetic algorithm

Truss shape and sizing optimization under frequency constraints is extremely useful when improving the dynamic performance of structures. However, coupling of two different types of design variables, nodal coordinates and cross-sectional areas, often lead to slow convergence or even divergence. Because shape and sizing variables coupled increase the number of design variables and the changes of shape and sizing variables are of widely different orders of magnitude. Otherwise, multiple frequency constraints often cause difficult dynamic sensitivity analysis. Thus optimal criteria and mathematical programming methods have considerable limitations on solving the problems because of needing complex dynamic sensitivity analysis and being easily trapped into the local optima. Genetic Algorithms (GAs) show great potentials to solve the truss shape and sizing optimization problems. Since GAs adopt global probabilistic population search techniques and require no gradient information. The improved genetic algorithms can effectively increase the solution quality. However, the serial GA is computationally expensive and is limited on gaining higher quality solutions. To solve the truss shape and sizing optimization problems with frequency constraints more effectively and efficiently, a Niche Hybrid Parallel Genetic Algorithm (NHPGA) is proposed to significantly reduce the computational cost and to further improve solution quality. The NHPGA is to blend the advantages of parallel computing, simplex search and genetic algorithm with niche technique. Several typical truss optimization examples demonstrate that NHPGA can significantly reduce computing time and attain higher quality solutions. It also suggests that the NHPGA provide a potential algorithm architecture, which effectively combines the robust and global search characteristics of genetic algorithm, strong exploitation ability of simplex search and computational speedup property of parallel computing.     

A tree-based particle swarm optimization for multicast routing

QoS multicast routing is a non-linear combinatorial optimization problem. It tries to find a multicast routing tree with minimal cost that can satisfy constraints such as bandwidth, delay, and delay jitter. This problem is NP-complete. The solution to such problems is often to search first for paths from the source node to each destination node and then integrate these paths into a multicast tree. Such a method, however, is slow and complex. To overcome these shortcomings, we propose a new method for tree-based optimization. Our algorithm optimizes the multicast tree directly, unlike the conventional solutions to finding paths and integrating them to generate a multicast tree. Our algorithm also applies particle swarm optimization to the solution to control the optimization orientation of the tree shape. Simulation results show that our algorithm performs well in searching, converging speed and adaptability scale.     

物流配送路径多目标优化的聚类-改进遗传算法

探讨运输车辆路线安排调度问题的解决方法，提出一种先用优先级综合聚类分析法将客户分类，再用带有控制开关系统的改进遗传算法求解多目标VRP的优化方法。构造了一种随机开关，以此控制遗传算法中的变异运算，增加了群体的多样性，避免了遗传算法中“局部最优现象”的发生。计算机仿真实验证明了该算法的有效性。