Exact Knowledge Hiding through Database Extension

In this paper, we propose a novel, exact border-based approach that provides an optimal solution for the hiding of sensitive frequent itemsets by (i) minimally extending the original database by a synthetically generated database part - the database extension, (ii) formulating the creation of the database extension as a constraint satisfaction problem, (iii) mapping the constraint satisfaction problem to an equivalent binary integer programming problem, (iv) exploiting underutilized synthetic transactions to proportionally increase the support of non-sensitive itemsets, (v) minimally relaxing the constraint satisfaction problem to provide an approximate solution close to the optimal one when an ideal solution does not exist, and (vi) by using a partitioning in the universe of the items to increase the efficiency of the proposed hiding algorithm. Extending the original database for sensitive itemset hiding is proved to provide optimal solutions to an extended set of hiding problems compared to previous approaches and to provide solutions of higher quality. Moreover, the application of binary integer programming enables the simultaneous hiding of the sensitive itemsets and thus allows for the identification of globally optimal solutions.     

A Generic Framework for Constrained Optimization Using Genetic Algorithms

In this paper, we propose a generic, two-phase framework for solving constrained optimization problems using genetic algorithms. In the first phase of the algorithm, the objective function is completely disregarded and the constrained optimization problem is treated as a constraint satisfaction problem. The genetic search is directed toward minimizing the constraint violation of the solutions and eventually finding a feasible solution. A linear rank-based approach is used to assign fitness values to the individuals. The solution with the least constraint violation is archived as the elite solution in the population. In the second phase, the simultaneous optimization of the objective function and the satisfaction of the constraints are treated as a biobjective optimization problem. We elaborate on how the constrained optimization problem requires a balance of exploration and exploitation under different problem scenarios and come to the conclusion that a nondominated ranking between the individuals will help the algorithm explore further, while the elitist scheme will facilitate in exploitation. We analyze the proposed algorithm under different problem scenarios using Test Case Generator-2 and demonstrate the proposed algorithm's capability to perform well independent of various problem characteristics. In addition, the proposed algorithm performs competitively with the state-of-the-art constraint optimization algorithms on 11 test cases which were widely studied benchmark functions in literature.     

Cooperative updating in the Hopfield model.

We propose a new method for updating units in the Hopfield model. With this method two or more units change at the same time, so as to become the lowest energy state among all possible states. Since this updating algorithm is based on the detailed balance equation, convergence to the Boltzmann distribution is guaranteed. If our algorithm is applied to finding the minimum energy in constraint satisfaction and combinatorial optimization problems, then there is a faster convergence than those with the usual algorithm in the neural network. This is shown by experiments with the travelling salesman problem, the four-color problem, the N-queen problem, and the graph bi-partitioning problem. In constraint satisfaction problems, for which earlier neural networks are effective in some cases, our updating scheme works fine. Even though we still encounter the problem of ending up in local minima, our updating scheme has a great advantage compared with the usual updating scheme used in combinatorial optimization problems. Also, we discuss parallel computing using our updating algorithm.     

Consistency techniques for continuous constraints

We consider constraint satisfaction problems with variables in continuous, numerical domains. Contrary to most existing techniques, which focus on computing one single optimal solution, we address the problem of computing a compact representation of the space of all solutions admitted by the constraints. In particular, we show how globally consistent (also called decomposable) labelings of a constraint satisfaction problem can be computed.Our approach is based on approximating regions of feasible solutions by 2 ^k -trees, a representation commonly used in computer vision and image processing. We give simple and stable algorithms for computing labelings with arbitrary degrees of consistency. The algorithms can process constraints and solution spaces of arbitrary complexity, but with a fixed maximal resolution.Previous work has shown that when constraints are convex and binary, path-consistency is sufficient to ensure global consistency. We show that for continuous domains, this result can be generalized to ternary and in fact arbitrary n-ary constraints using the concept of (3,2)-relational consistency. This leads to polynomial-time algorithms for computing globally consistent labelings for a large class of constraint satisfaction problems with continuous variables.     

An improved branch‐and‐bound clustering approach for data partitioning

In this paper, we are concerned with clustering algorithms for vertical partitioning. In particular, we examine the use of a branch‐and‐bound scheme. An existing algorithm using such a scheme may produce infeasible solutions to some problems. We adopt the same branch‐and‐bound scheme and develop a new branching strategy to avoid infeasibility. Illustrative examples are used to demonstrate the effectiveness of our new approach. In addition, we also show how to formulate the horizontal partitioning problem such that the same algorithm can be applied.     

A graph-based immune-inspired constraint satisfaction search

We propose an artificial immune algorithm to solve constraint satisfaction problems (CSPs). Recently, bio-inspired algorithms have been proposed to solve CSPs. They have shown to be efficient in solving hard problem instances. Given that recent publications indicate that immune-inspired algorithms offer advantages to solve complex problems, our main goal is to propose an efficient immune algorithm which can solve CSPs. We have calibrated our algorithm using relevance estimation and value calibration (REVAC), which is a new technique recently introduced to find the parameter values for evolutionary algorithms. The tests were carried out using randomly generated binary constraint satisfaction problems and instances of the three-colouring problem with different constraint networks. The results suggest that the technique may be successfully applied to solve CSPs.     

两种改进的模拟退火算法求解大值域约束满足问题

随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点。RB模型（Revised B）是一个非平凡的随机约束满足问题,它具有精确的可满足性相变现象和极易产生难解实例这两个重要特征。针对RB模型这一类具有大值域的随机约束满足问题,提出了两种基于模拟退火的改进算法即RSA（Revised Simulated Annealing Algorithm）和GSA（Genetic-simulated Annealing Algorithm）。将这两种算法用于求解RB模型的随机实例,数值实验结果表明：在进入相变区域时,RSA和GSA算法依然可以有效地找到随机实例的解,并且在求解效率上明显优于随机游走算法。在接近相变阈值点时,由这两种算法得到的最优解仅使得极少数的约束无法满足。     

Control variable parameterisation with penalty approach for hypersonic vehicle reentry optimisation

An efficient trajectory optimisation approach combining the classical control variable parameterisation (CVP) with a novel smooth technology and two penalty strategies is developed to solve the trajectory optimal control problems. Since it is difficult to deal with path constraints in CVP method, the novel smooth technology is firstly employed to transform the complex constraints into one smooth constraint. Then, two penalty strategies are proposed to tackle the converted path and terminal constraints to decrease the computational complexity and improve the constraints satisfaction. Finally, a nonlinear programming problem, which approximates the original trajectory optimisation problem, is obtained. Error analysis shows that the proposed method has good convergence property. A general hypersonic cruise vehicle trajectory optimisation example is employed to test the performance of the proposed method. Numerical results show that the path and terminal conditions are well satisfied and better trajectory profiles are obtained, showing the effectiveness of the proposed method.     

Optimum synthesis of a four-bar mechanism using the modified bacterial foraging algorithm

This paper presents the mechanical synthesis of a four-bar mechanism, its definition as a constrained optimisation problem in the presence of one dynamic constraint and its solution with a swarm intelligence algorithm based on the bacteria foraging process. The algorithm is adapted to solve the optimisation problem by adding a suitable constraint-handling technique that is able to incorporate a selection criterion for the two objectives stated by the kinematic analysis of the problem. Moreover, a diversity mechanism, coupled with the attractor operator used by bacteria, is designed to favour the exploration of the search space. Four experiments are designed to validate the proposed model and to test the performance of the algorithm regarding constraint-satisfaction, sub-optimal solutions obtained, performance metrics and an analysis of the solutions based on the simulation of the four-bar mechanism. The results are compared with those provided by four algorithms found in the specialised literature used to solve mechanical design problems. On the basis of the simulation analysis, the solutions obtained by the proposed algorithm lead to a more suitable design based on motion generation and operation quality.     

Algorithmic aspects of area-efficient hardware/software partitioning

Area efficiency is one of the major considerations in constraint aware hardware/software partitioning process. This paper focuses on the algorithmic aspects for hardware/software partitioning with the objective of minimizing area utilization under the constraints of execution time and power consumption. An efficient heuristic algorithm running in O(n log n) is proposed by extending the method devised for solving the 0-1 knapsack problem. Also, an exact algorithm based on dynamic programming is proposed to produce the optimal solution for small-sized problems. Simulation results show that the proposed heuristic algorithm yields very good approximate solutions while dramatically reducing the execution time.     

Cauchy Grey Wolf Optimiser for continuous optimisation problems

ABSTRACT

Grey Wolf Optimiser (GWO) is a recently developed optimisation approach to solve complex non-linear optimisation problems. It is relatively simple and leadership-hierarchy based approach in the class of Swarm Intelligence based algorithms. For solving complex real-world non-linear optimisation problems, the search equation provided in GWO is not of sufficient explorative behaviour. Therefore, in the present paper, an attempt has been made to increase the exploration capability along with the exploitation of a search space by proposing an improved version of classical GWO. The proposed algorithm is named as Cauchy-GWO. In Cauchy-GWO Cauchy operator has been integrated in which first two new wolves are generated with the help of Cauchy distributed random numbers and then another new wolf is generated by taking the convex combination of these new wolves. The performance of Cauchy-GWO is exhibited on standard IEEE CEC 2014 benchmark problem set. Statistical analysis of the results on CEC 2014 benchmark set and popular evaluation criteria, Performance Index (PI) proves that Cauchy-GWO outperforms GWO in terms of error values defined in IEEE CEC 2014 benchmarks collection. Later on in the paper, GWO and Cauchy-GWO algorithms have been used to solve three well-known engineering application problems and two problems of reliability. From the analysis conducted in the present paper, it can be concluded that the proposed algorithm, Cauchy-GWO is reliable and efficient algorithm to solve continuous benchmark test problems, as well as real-life applications problems.     

Earliness–tardiness minimization on a single machine to schedule preventive maintenance tasks: metaheuristic and exact methods

In this paper, we consider the problem of scheduling a set of M preventive maintenance tasks to be performed on M machines. The machines are assigned to execute production tasks. We aim to minimize the total preventive maintenance cost such that the maintenance tasks have to continuously be run during the schedule horizon. Such a constraint holds when the maintenance resources are not sufficient. We solve the problem by two exact methods and meta-heuristic algorithms. As exact procedures we used linear programming and branch and bound methods. As meta-heuristics, we propose a local search approach as well as a genetic algorithm. Computational experiments are performed on randomly generated instances to show that the proposed methods produce appropriate solutions for the problem. The computational results show that the deviation of the meta-heuristics solutions to the optimal one is very small, which confirms the effectiveness of meta-heuristics as new approaches for solving hard scheduling problems.     

A hybrid approach for multi-objective combinatorial optimisation problems in ship design and shipping

Numerous real-world problems relating to ship design and shipping are characterised by combinatorially explosive alternatives as well as multiple conflicting objectives and are denoted as multi-objective combinatorial optimisation (MOCO) problems. The main problem is that the solution space is very large and therefore the set of feasible solutions cannot be enumerated one by one. Current approaches to solve these problems are multi-objective metaheuristics techniques, which fall in two categories: population-based search and trajectory-based search. This paper gives an overall view for the MOCO problems in ship design and shipping where considerable emphasis is put on evolutionary computation and the evaluation of trade-off solutions. A two-stage hybrid approach is proposed for solving a particular MOCO problem in ship design, subdivision arrangement of a ROPAX vessel. In the first stage, a multi-objective genetic algorithm method is employed to approximate the set of pareto-optimal solutions through an evolutionary optimisation process. In the subsequent stage, a higher-level decision-making approach is adopted to rank these solutions from best to worst and to determine the best solution in a deterministic environment with a single decision maker.     

A Connectionist Approach for Solving Large Constraint Satisfaction Problems

An efficient neural network technique is presented for the solution of binary constraint satisfaction problems. The method is based on the application of a double-update technique to the operation of the discrete Hopfield-type neural network that can be constructed for the solution of such problems. This operation scheme ensures that the network moves only between consistent states, such that each problem variable is assigned exactly one value, and leads to a fast and efficient search of the problem state space. Extensions of the proposed method are considered in order to include several optimisation criteria in the search. Experimental results concerning many real-size instances of the Radio Links Frequency Assignment Problem demonstrate very good performance.     

Concurrent product configuration and process planning: Some optimization experimental results

In nowadays industrial competition, optimizing concurrently the configured product and the planning of its production process becomes a key issue in order to achieve mass customization development. However, if many studies have addressed these two problems separately, very few have considered them concurrently. We therefore consider in this article a multi-criteria optimization problem that follows an interactive configuration and planning process. The configuration and planning problems are considered as constraint satisfaction problems (CSPs). After some recalls about this two-step approach, we propose to evaluate a recent evolutionary optimization algorithm called CFB-EA (for constraint filtering based evolutionary algorithm). CFB-EA, specially designed to handle constrained problems, is compared with an exact branch and bound approach on small problem instances and with another evolutionary approach carefully selected for larger instances. Various experiments, with solutions spaces up to 10¹⁷, permit us to conclude that CFB-EA sounds very promising for the concurrent optimization of a configured product and its production process.     

Maintenance scheduling problems as benchmarks for constraint algorithms

The paper focuses on evaluating constraint satisfaction search algorithms on application based random problem instances. The application we use is a well-studied problem in the electric power industry: optimally scheduling preventive maintenance of power generating units within a power plant. We show how these scheduling problems can be cast as constraint satisfaction problems and used to define the structure of randomly generated non-binary CSPs. The random problem instances are then used to evaluate several previously studied algorithms. The paper also demonstrates how constraint satisfaction can be used for optimization tasks. To find an optimal maintenance schedule, a series of CSPs are solved with successively tighter cost-bound constraints. We introduce and experiment with an “iterative learning” algorithm which records additional constraints uncovered during search. The constraints recorded during the solution of one instance with a certain cost-bound are used again on subsequent instances having tighter cost-bounds. Our results show that on a class of randomly generated maintenance scheduling problems, iterative learning reduces the time required to find a good schedule. This revised version was published online in June 2006 with corrections to the Cover Date.     

约束可满足性中求解RB模型实例的算法综述

约束满足问题是人工智能领域中最基本的NP完全问题之一。多年来,随着约束满足问题的深入研究,国内外学者提出多种实例模型。其中,RB模型是一种能生成具有精确相变的增长域约束满足问题实例,其求解难度极具挑战性。为了寻找其求解的新型高效算法,促进约束可满足问题的RB模型求解算法领域的研究,首先从约束满足问题的模型发展、求解技术进行分析;其次,对各类求解RB模型实例算法进行梳理,将求解的算法文献划分为回溯启发式类、信息传播类和元启发式类相关改进算法,从算法原理、改进策略、收敛性和精确度等方面进行对比综述;最后给出求解RB模型实例算法的研究趋势和发展方向。     

Classes of submodular constraints expressible by graph cuts

Submodular constraints play an important role both in theory and practice of valued constraint satisfaction problems (VCSPs). It has previously been shown, using results from the theory of combinatorial optimisation, that instances of VCSPs with submodular constraints can be minimised in polynomial time. However, the general algorithm is of order O(n ⁶) and hence rather impractical. In this paper, by using results from the theory of pseudo-Boolean optimisation, we identify several broad classes of submodular constraints over a Boolean domain which are expressible using binary submodular constraints, and hence can be minimised in cubic time. Furthermore, we describe how our results translate to certain optimisation problems arising in computer vision.     

Seeker optimisation (human group optimisation) algorithm with chaos

Seeker optimisation algorithm (SOA), also referred to as human group metaheuristic optimisation algorithms form a very hot area of research, is an emerging population-based and gradient-free optimisation tool. It is inspired by searching behaviour of human beings in finding an optimal solution. The principal shortcoming of SOA is that it is easily trapped in local optima and consequently fails to achieve near-global solutions in complex optimisation problems. In an attempt to relieve this problem, in this article, chaos-based strategies are embedded into SOA. Five various chaotic-based SOA strategies with four different chaotic map functions are examined and the best strategy is chosen as the suitable chaotic scheme for SOA. The results of applying the proposed chaotic SOA to miscellaneous benchmark functions confirm that it provides accurate solutions. It surpasses basic SOA, genetic algorithm, gravitational search algorithm variant, cuckoo search optimisation algorithm, firefly swarm optimisation and harmony search the proposed chaos-based SOA is expected successfully solve complex engineering optimisation problems.