Conflict-based pruning of a solution space within a constructive geometric constraint solver

The Computer-Aided Design field has developed sketching systems that automatically instantiate geometric objects from a rough sketch, annotated with dimensions and constraints input by the user. Geometric problems defined by constraints have an exponential number of solution instances in the number of geometric elements involved. The user is only interested in the intended solution that, besides fulfilling the geometric constraints, exhibits some additional properties. Metaheuristics have been successfully applied to solve this problem named as Root Identification Problem. However, these methods are very time-consuming because of the time required to evaluate every candidate solution. Pruning the search space is paramount to simplify the number of solution instances evaluated before finding the intended solution. In this work, we present an algorithm for pruning based on the detection of conflicts, i.e. patterns that drive to non-feasible solutions. Subsequent solutions will not be evaluated in case of matching a neighborhood corresponding to a previously detected conflicting pattern. The algorithm may be integrated in the evaluation phase of techniques that dynamically explore the search space, like metaheuristics, significantly improving the required computational time.     

Evolutionary algorithms for route selection and rate allocation in multirate multicast networks

In multirate multicasting, different users (receivers) in the same multicast group can receive service at different rates, depending on the user requirements and the network congestion level. Compared with unirate multicasting, this provides more flexibility to the users and allows more efficient usage of the network resources. In this paper, we simultaneously address the route selection and rate allocation problem in multirate multicast networks; that is, the problem of constructing multiple multicast trees and simultaneously allocating the rate of receivers for maximizing the sum of utilities over all receivers, subject to link capacity and delay constraints for high-bandwidth delay-sensitive applications in point-to-point communication networks. We propose a genetic algorithm for this problem and elaborate on many of the elements in order to improve solution quality and computational efficiency in applying the proposed methods to the problem. These include the genetic representation, evaluation function, genetic operators, and procedure. Additionally, a new method using an artificial intelligent search technique, called the coevolutionary algorithm, is proposed to achieve better solutions, and methods of selecting environmental individuals and evaluating fitness are developed. The results of extensive computational simulations show that the proposed algorithms provide high-quality solutions and outperform existing approach.     

面向无线内容分发网络的树形拓扑生成算法

在无线内容分发网络中,为减轻骨干网络的传输压力,可将网络拓扑结构构建为以基站和Wi Fi接入点为根的若干棵最小生成树,并对生成树的深度和每个节点的度数进行约束。这种深度和度数约束的最小生成树问题是一个NP完全问题。针对该问题,首先提出能够生成优质近似解的启发式算法,该算法在不违反深度以及度数约束的情况下构建生成树,算法思想为在服务性节点相连的边中选择与当前生成树相连且权值最小的边加入生成树。然后在生成初始近似解的基础上采用定制的禁忌搜索算法和模拟退火算法对该近似解实施进一步优化。实验结果表明,在给定的约束条件下,禁忌搜索算法求得的解优于现有的遗传算法,在深度约束为4以及度数约束为10的条件下,解的改进幅度可达18.5%,所提算法的运行速度比遗传算法提高了10倍。     

Breaking symmetries in graph search with canonizing sets

There are many complex combinatorial problems which involve searching for an undirected graph satisfying given constraints. Such problems are often highly challenging because of the large number of isomorphic representations of their solutions. This paper introduces effective and compact, complete symmetry breaking constraints for small graph search. Enumerating with these symmetry breaks generates all and only non-isomorphic solutions. For small search problems, with up to 10 vertices, we compute instance independent symmetry breaking constraints. For small search problems with a larger number of vertices we demonstrate the computation of instance dependent constraints which are complete. We illustrate the application of complete symmetry breaking constraints to extend two known sequences from the OEIS related to graph enumeration. We also demonstrate the application of a generalization of our approach to fully-interchangeable matrix search problems.     

Making constraint solvers more usable: overconstraint problem

The richness and expressive power of geometric constraints causes unintended ambiguities and inconsistencies during their solution or realization. For example, geometric constraint problems may turn out to be overconstrained requiring the user to delete one or more of the input constraints, and the solutions must then be dynamically updated. Without proper guidance by the constraint solver, the user must have profound insight into the mathematical nature of constraint systems and understand the internals of the solver algorithm. But a general user is most likely unfamiliar with those problems, so that the required interaction with the constraint solver may well be beyond the user's ability. In this paper, we present strategies and techniques to empower the user to deal effectively with the overconstraint problem while not requiring him or her to become an expert in the mathematics of constraint solving.We formulate this problem as a series of formal requirements that gel with other essentials of constraint solvers. We then give algorithmic solutions that are both general and efficient (running time typically linear in the number of relevant constraints).     

Computing minimal mappings between lightweight ontologies

As a valid solution to the semantic heterogeneity problem, many matching solutions have been proposed. Given two lightweight ontologies, we compute the minimal mapping, namely the subset of all possible correspondences, that we call mapping elements, between them such that (i) all the others can be computed from them in time linear in the size of the input ontologies and (ii) none of them can be dropped without losing property (i). We provide a formal definition of minimal mappings and define a time efficient computation algorithm which minimizes the number of comparisons between the nodes of the two input ontologies. The experimental results show a substantial improvement both in the computation time and in the number of mapping elements which need to be handled, for instance for validation, navigation, and search.     

A modified genetic algorithm for the flow shop sequencing problem to minimize mean flow time

A modified genetic algorithm (MGA) is developed for solving the flow shop sequencing problem with the objective of minimizing mean flow time. To improve the general genetic algorithm (GA) procedure, two additional operations are introduced into the algorithm. One replaces the worst solutions in each generation with the best solutions found in previous generations. The other improves the most promising solution, through local search, whenever the best solution has not been updated for a certain number of generations. Computational experiments on randomly generated problems are carried out to compare the MGA with the general GA and special-purpose heuristics. The results show that the MGA is superior to general GA in solution quality with similar computation times. The MGA solutions are also better than those given by special-purpose heuristics though MGA takes longer computation time.     

基于深度邻域搜索PSO 算法的装配序列优化问题

针对产品结构特征建立几何约束矩阵, 以最大化满足几何约束条件装配次数和最小化装配方向改变次数为目标, 研究产品装配序列优化问题. 利用值变换的粒子位置和速度更新规则, 基于具有随机性启发式算法产生初始种群, 提出一种带有深度邻域搜索改进策略的粒子群算法解决装配序列问题. 通过装配实例验证了所提出算法的性能并对装配序列质量进行了评价, 所得结果表明了该算法在解决装配序列优化问题上的有效性与稳定性.

     

A hyper-heuristic based framework for dynamic optimization problems

Most of the real world problems have dynamic characteristics, where one or more elements of the underlying model for a given problem including the objective, constraints or even environmental parameters may change over time. Hyper-heuristics are problem-independent meta-heuristic techniques that are automating the process of selecting and generating multiple low-level heuristics to solve static combinatorial optimization problems. In this paper, we present a novel hybrid strategy for applicability of hyper-heuristic techniques on dynamic environments by integrating them with the memory/search algorithm. The memory/search algorithm is an important evolutionary technique that have applied on various dynamic optimization problems. We validate performance of our method by considering both the dynamic generalized assignment problem and the moving peaks benchmark. The former problem is extended from the generalized assignment problem by changing resource consumptions, capacity constraints and costs of jobs over time; and the latter one is a well-known synthetic problem that generates and updates a multidimensional landscape consisting of several peaks. Experimental evaluation performed on various instances of the given two problems validates that our hyper-heuristic integrated framework significantly outperforms the memory/search algorithm.     

基于遗传算法的焊接生产线工位平衡规划方法

在现代化大规模大批量的流水装配制造业中,数量众多的作用分配和多工位的合理安排使工位平衡问题显得更为突出。针对第一类工位平衡问题,即在给定的生产节拍下最小化工位数,首先分析了该问题并建立了数学模型,进而提出了一种基于改进遗传算法求解工位平衡问题的方法。该算法以焊接任务的操作顺序优先关系为约束前提,在初始种群的生产以及交叉和变异过程中保证了染色体解的可行性,同时在遗传算法的选择过程中考虑了具有相同工位数的最优作业方案的工时标准差,从而提高了算法的搜索效率和解的可靠性。最后通过实例求解验证了该算法的有效性。     

Timetabling through Constrained Heuristic Search and Genetic Algorithms

Hybrid genetic algorithms are presented that use constrained heuristic search and genetic techniques for the timetabling problem (TP). The TP is an NP-hard problem for which a general polynomial time deterministic algorithm is not known. The paper describes the classification of constraints and the constraint ordering to obtain the minimization of backtracking and the maximization of parallelism. The school timetabling problem is discussed in detail as a case study. The genetic algorithm approach is particularly well suited to this kind of problem, since there exists an easy way to assess a good timetable, but not a well structured automatic technique for constructing it. So, a population of timetables is created that evolves toward the best solution. The evaluation function and the genetic operators are well separated from the domain-specific parts, such as the knowledge of the problem and the heuristics, i.e. from the timetable builder. The present paper illustrates an approach based on the hybridization of constrained heuristic search with novel genetic algorithm techniques. It compares favourably with known programs to solve decision problems under logic constraints. The cost of the new algorithm and the quality of the solutions obtained in significant experiments are reported.     

Geometric primitive extraction using a genetic algorithm

Extracting geometric primitives from geometric sensor data is an important problem in model-based vision. A minimal subset is the smallest number of points necessary to define a unique instance of a geometric primitive. A genetic algorithm based on a minimal subset representation is used to perform primitive extraction. It is shown that the genetic approach is an improvement over random search and is capable of extracting more complex primitives than the Hough transform     

应用改进型遗传算法进行药物分子对接设计

文章建立了一种约束优化的演化模型,并构造出求解此模型的多种群空间收缩遗传算法,将信息熵概念引入进化过程,控制各种群寻优搜索时解空间的收缩。该算法用种群的多样性避免遗传进化的早熟现象,并以空间收缩尺度作为停机判椐,有效地控制了算法的收敛。利用基于小种群的多种群进化策略,在保证种群多样性的前提下,极大程度地减少了计算量,提高了计算效率。数值算例表明,熵的介入增强了随机搜索类进化算法的寻优目的性,使收敛过程平稳且迅速。算例表明此算法能有效的应用于药物分子对接设计。     

Heuristics for the capacitated dispersion problem

In this paper, we investigate the adaptation of the greedy randomized adaptive search procedure (GRASP) and variable neighborhood descent (VND) methodologies to the capacitated dispersion problem. Dispersion and diversity problems arise in the placement of undesirable facilities, workforce management, and social media, among others. Maximizing diversity deals with selecting a subset of elements from a given set in such a way that the distance among the selected elements is maximized. We target here a realistic variant with capacity constraints for which a heuristic with a performance guarantee was previously introduced. In particular, we propose a hybridization of GRASP and VND implementing within the strategic oscillation framework. To evaluate the performance of our heuristic, we perform extensive experimentation to first set key search parameters, and then compare the final method with the previous heuristic. Additionally, we propose a mathematical model to obtain optimal solutions for small‐sized instances, and compare our solutions with the well‐known LocalSolver software.     

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.     

Evolving structural design solutions using an implicit redundant Genetic Algorithm

Performing synthesis during conceptual design provides substantial cost savings by selecting an efficient design topology and geometry, in addition to selecting the structural member properties. A new evolutionary-based representation, which combines redundancy and implicit fitness constraints, is introduced to represent and search for design solutions in an unstructured, multi-objective structural frame problem. The implicit redundant representation genetic algorithm, in tandem with the unstructured problem domain definition, allows the evaluation of diverse frame topologies and geometries. The IRR GA allows the representation of a variable number of location independent parameters, which overcomes the fixed parameter limitations of standard GAs. The novel frame designs evolved by the IRR GA synthesis design method compare favourably with traditional frame design solutions calculated by trial and error. Received May 27, 1999     

约束优化问题的改进遗传算法设计

遗传算子是影响遗传算法优化效果的重要因素,针对目前遗传算法研究中对约束优化问题求解的不足,提出基于退火思想的退火选择算子和加权适应度算子,并给出了退火选择算子和加权适应度算子设计方法及其计算过程.在此基础上与现有的遗传算子结合,提出一种新的改进遗传算法,分析了改进遗传算法与基于罚函数遗传算法之间在原理上的区别.最后以两个测试函数为算例对算法进行了性能测试,结果表明改进的遗传算法具有良好的优化性能,能获得更好的优化结果.     

A Lagrangian Approach for Multiple Personalized Campaigns

The multicampaign assignment problem is a campaign model to overcome the multiple-recommendation problem that occurs when conducting several personalized campaigns simultaneously. In this paper, we propose a Lagrangian method for the problem. The original problem space is transformed to another simpler one by introducing Lagrange multipliers, which relax the constraints of the multicampaign assignment problem. When the Lagrangian vector is supplied, we can compute the optimal solution under this new environment in O(NK2) time, where N and K are the numbers of customers and campaigns, respectively. This is a linear-time method when the number of campaigns is constant. However, it is not easy to find a Lagrangian vector in exact accord with the given problem constraints. We thus combine the Lagrangian method with a genetic algorithm to find good near-feasible solutions. We verify the effectiveness of our evolutionary Lagrangian approach in both theoretical and experimental viewpoints. The suggested Lagrangian approach is practically attractive for large-scale real-world problems.     

Automatic parameter tuning with a Bayesian case-based reasoning system. A case of study

The parameter setting of an algorithm that will result in optimal performance differs across problem instance domains. Users spend a lot of time tuning algorithms for their specific problem domain, and this time could be saved by an automatic approach for parameter tuning.In this paper, we present a system that recommends the parameter configuration of an algorithm that solves a problem, conditioned by the particular features of the current problem instance to be solved. The proposed system is based on a basic adjustment model designed by authors (Pavon, R., Díaz, F., & Luzón, V. (2008). A model for parameter setting based on Bayesian networks. Engineering Applications of Artificial Intelligence, 21(1), 14–25) in which starting from experimental results concerning the search for solutions to several instances of the problem, a Bayesian network (BN) is induced and tries to infer the best configuration for the algorithm used.However, taking into account that the optimal parameter configuration may differ considerably across problem instances of a specific domain, the present work extends the former incorporating additional information about problem instances and using the case-based reasoning (CBR) methodology as the framework integrator for the different instances from the same problem, where each problem instance deals with a specific BN. In this way, the system will automatically recommend a parameter configuration for a given algorithm according to the characteristics of the problem instance at hand and past experience of similar instances.As an example, we empirically evaluate our Bayesian CBR system to tune a genetic algorithm for solving the root identification problem. The experimental results demonstrate the validity of the model proposed.     

Evolutionary Optimization of File Assignment for a Large-Scale Video-on-Demand System

We present a genetic algorithm for tackling a file assignment problem for a large-scale video-on-demand system. The file assignment problem is to find the optimal replication and allocation of movie files to disks so that the request blocking probability is minimized subject to capacity constraints. We adopt a divide-and-conquer strategy, where the entire solution space of file assignments is divided into subspaces. Each subspace is an exclusive set of solutions sharing a common file replication instance. This allows us to utilize a greedy file allocation method for finding a good-quality heuristic solution within each subspace. We further design two performance indices to measure the quality of the heuristic solution on 1.) its assignment of multicopy movies and 2.) its assignment of single-copy movies. We demonstrate that these techniques, together with ad hoc population handling methods, enable genetic algorithms to operate in a significantly reduced search space and achieve good-quality file assignments in a computationally efficient way.