Bi-objective optimisation model for installation scheduling in offshore wind farms

A bi-objective optimisation using a compromise programming approach is proposed for installation scheduling of an offshore wind farm. As the installation cost and the completion period of the installation are important aspects in the construction of an offshore wind farm, the proposed method is used to deal with those conflicting objectives. We develop a mathematical model using integer linear programming (ILP) to determine the optimal installation schedule considering several constraints such as weather condition and the availability of vessels. We suggest two approaches to deal with the multi-objective installation scheduling problem, namely compromise programming with exact method and with metaheuristic techniques. In the exact method the problem is solved by CPLEX whereas in the metaheuristic approach we propose Variable Neighbourhood Search (VNS) and Simulated Annealing (SA). Moreover, greedy algorithms and a local search for solving the scheduling problem are introduced. Two generated datasets are used for testing our approaches. The computational experiments show that the proposed metaheuristic approaches produce interesting results as the optimal solution for some cases is obtained.     

选择策略对遗传归纳逻辑程序设计收敛性能的影响

采用遗传算法（GA）作为归纳逻辑程序设计（ILP）的搜索策略，可以提高ILP方法的鲁棒性和适应性，文章简要叙述了对作者提出的遗传归纳逻辑程序设计（GILP）算法作的改进，测试了选择策略对GILP算法收敛性能的影响，采用不同的选择策略不会影响算法的最终收敛结果，但会产生不同的选择压力，导致算法具有不同的收敛速率。     

A genetic algorithm based region sampling for selection of local features in handwritten digit recognition application

Identification of local regions from where optimal discriminating features can be extracted is one of the major tasks in the area of pattern recognition. To locate such regions different kind of region sampling techniques are used in the literature. There is no standard methodology to identify exactly such regions. Here we have proposed a methodology where local regions of varying heights and widths are created dynamically. Genetic algorithm (GA) is then applied on these local regions to sample the optimal set of local regions from where an optimal feature set can be extracted that has the best discriminating features. We have evaluated the proposed methodology on a data set of handwritten Bangla digits. In the present work, we have randomly generated seven sets of local regions and from every set, GA selects an optimal group of local regions which produces best recognition performance with a support vector machine (SVM) based classifier. Other popular optimization techniques like simulated annealing (SA) and hill climbing (HC) have also been evaluated with the same data set and maximum recognition accuracies were found to be 97%, 96.7% and 96.7% for GA, SA and HC, respectively. We have also compared the performance of the present technique with those of other zone based techniques on the same database.     

The fixed set search applied to the power dominating set problem

In this article, we focus on solving the power dominating set problem and its connected version. These problems are frequently used for finding optimal placements of phasor measurement units in power systems. We present an improved integer linear program (ILP) for both problems. In addition, a greedy constructive algorithm and a local search are developed. A greedy randomised adaptive search procedure (GRASP) algorithm is created to find near optimal solutions for large scale problem instances. The performance of the GRASP is further enhanced by extending it to the novel fixed set search (FSS) metaheuristic. Our computational results show that the proposed ILP has a significantly lower computational cost than existing ILPs for both versions of the problem. The proposed FSS algorithm manages to find all the optimal solutions that have been acquired using the ILP. In the last group of tests, it is shown that the FSS can significantly outperform the GRASP in both solution quality and computational cost.     

A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system

Effective task scheduling, which is essential for achieving high performance in a heterogeneous multiprocessor system, remains a challenging problem despite extensive studies. In this article, a heuristic-based hybrid genetic-variable neighborhood search algorithm is proposed for the minimization of makespan in the heterogeneous multiprocessor scheduling problem. The proposed algorithm distinguishes itself from many existing genetic algorithm (GA) approaches in three aspects. First, it incorporates GA with the variable neighborhood search (VNS) algorithm, a local search metaheuristic, to exploit the intrinsic structure of the solutions for guiding the exploration process of GA. Second, two novel neighborhood structures are proposed, in which problem-specific knowledge concerned with load balancing and communication reduction is utilized respectively, to improve both the search quality and efficiency of VNS. Third, the proposed algorithm restricts the use of GA to evolve the task-processor mapping solutions, while taking advantage of an upward-ranking heuristic mostly used by traditional list scheduling approaches to determine the task sequence assignment in each processor. Empirical results on benchmark task graphs of several well-known parallel applications, which have been validated by the use of non-parametric statistical tests, show that the proposed algorithm significantly outperforms several related algorithms in terms of the schedule quality. Further experiments are carried out to reveal that the proposed algorithm is able to maintain high performance within a wide range of parameter settings.     

A genetic algorithm-based approach for solving the resource-sharing and scheduling problem

We introduce a heuristic that is based on a unique genetic algorithm (GA) to solve the resource-sharing and scheduling problem (RSSP). This problem was previously formulated as a continuous-time mixed integer linear programming model and was solved optimally using a branch-and-bound (B&B) algorithm. The RSSP considers the use of a set of resources for the production of several products. Producing each product requires a set of operations with precedence relationships among them. Each operation can be performed using alternative modes which define the subset of the resources needed, and an operation may share different resources simultaneously. The problem is to select a single mode for each operation and accordingly to schedule the resources, while minimizing the makespan time. The GA we propose is based on a new encoding schema that adopts the structure of a DNA in nature. In our experiments we compared the effectiveness and runtime of our GA versus a B&B algorithm and two truncated B&B algorithms that we developed on a set of 118 problem instances. The results demonstrate that the GA solved all the problems (10 runs each), and reaches optimality in 75% of the runs, had an average deviation of less than 1% from the optimal makespan, and a runtime that was much less sensitive to the size of the problem instance.     

Two effective hybrid metaheuristic algorithms for minimization of multimodal functions

Global optimization problems naturally arise from many applications. We propose two hybrid metaheuristic algorithms for finding a global optimum of a continuous function. Our proposed algorithms are hybridizations of genetic algorithm (GA) and variable neighbourhood search (VNS). To increase the efficiency of our algorithms, for smooth functions we present an effective locally improving line search procedure, and for non-smooth functions, we use the simplex method proposed by Nelder and Mead. By use of the recently adopted non-parametric statistical tests of Kruskal–Wallis and Mann–Whitney for analysing the behaviour of evolutionary algorithms, we compare both the efficiency and the effectiveness of our proposed algorithms with efficiently representative metaheuristic algorithms such as the multiagent GA proposed by Liang et al., the ant colony algorithm proposed by Toksari, and the VNS of Toksari and Güner on a variety of standard test functions. Computational experiments demonstrate that our proposed algorithms are efficiently effective.     

Hybrid techniques based on solving reduced problem instances for a longest common subsequence problem

Finding the longest common subsequence of a given set of input strings is a relevant problem arising in various practical settings. One of these problems is the so-called longest arc-preserving common subsequence problem. This NP-hard combinatorial optimization problem was introduced for the comparison of arc-annotated ribonucleic acid (RNA) sequences. In this work we present an integer linear programming (ILP) formulation of the problem. As even in the context of rather small problem instances the application of a general purpose ILP solver is not viable due to the size of the model, we study alternative ways based on model reduction in order to take profit from this ILP model. First, we present a heuristic way for reducing the model, with the subsequent application of an ILP solver. Second, we propose the application of an iterative hybrid algorithm that makes use of an ILP solver for generating high quality solutions at each iteration. Experimental results concerning artificial and real problem instances show that the proposed techniques outperform an available technique from the literature.     

Flow shop scheduling to minimize the total completion time with a permanently present operator: Models and ant colony optimization metaheuristic

This paper studies the one-operator m-machine flow shop scheduling problem with the objective of minimizing the total completion time. In this problem, the processing of jobs and setup of machines require the continuous presence of a single operator. We compare three different mathematical formulations and propose an ant colony optimization based metaheuristic to solve this flow shop scheduling problem. A series of experiments are carried out to compare the properties of three formulations and to investigate the performance of the proposed ant colony optimization metaheuristic. The computational results show that (1) an assignment-based formulation performs best, and (2) the ant colony optimization based metaheuristic is a computationally efficient algorithm.     

Branch and bound for the cutwidth minimization problem

The cutwidth minimization problem consists of finding a linear arrangement of the vertices of a graph where the maximum number of cuts between the edges of the graph and a line separating consecutive vertices is minimized. We first review previous approaches for special classes of graphs, followed by lower bounds and then a linear integer formulation for the general problem. We then propose a branch-and-bound algorithm based on different lower bounds on the cutwidth of partial solutions. Additionally, we introduce a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic to obtain good initial solutions. The combination of the branch-and-bound and GRASP methods results in optimal solutions or a reduced relative gap (difference between upper and lower bounds) on the instances tested. Empirical results with a collection of previously reported instances indicate that the proposed algorithm is able to solve all the small instances (up to 32 vertices) as well as some of the large instances tested (up to 158 vertices) using less than 30 minutes of CPU time. We compare the results of our method with previous lower bounds, and with the best previous linear integer formulation solved using Cplex. Both comparisons favor the proposed procedure.     

Using differential evolution for fine tuning naïve Bayesian classifiers and its application for text classification

The Naive Bayes (NB) learning algorithm is simple and effective in many domains including text classification. However, its performance depends on the accuracy of the estimated conditional probability terms. Sometimes these terms are hard to be accurately estimated especially when the training data is scarce. This work transforms the probability estimation problem into an optimization problem, and exploits three metaheuristic approaches to solve it. These approaches are Genetic Algorithms (GA), Simulated Annealing (SA), and Differential Evolution (DE). We also propose a novel DE algorithm that uses multi-parent mutation and crossover operations (MPDE) and three different methods to select the final solution. We create an initial population by manipulating the solution generated by a method used for fine tuning the NB. We evaluate the proposed methods by using their resulted solutions to build NB classifiers and compare their results with the results of obtained from classical NB and Fine-Tuning Naïve Bayesian (FTNB) algorithm, using 53 UCI benchmark data sets. We name these obtained classifiers NBGA, NBSA, NBDE, and NB-MPDE respectively. We also evaluate the performance NB-MPDE for text-classification using 18 text-classification data sets, and compare its results with the results of obtained from FTNB, BNB, and MNB. The experimental results show that using DE in general and the proposed MPDE algorithm in particular are more convenient for fine-tuning NB than all other methods, including the other two metaheuristic methods (GA, and SA). They also indicate that NB-MPDE achieves superiority over classical NB, FTNB, NBDE, NBGA, NBSA, MNB, and BNB.     

Models and algorithms for packing rectangles into the smallest square

We consider the problem of determining the smallest square into which a given set of rectangular items can be packed without overlapping. We present an ILP model, an exact approach based on the iterated execution of a two-dimensional packing algorithm, and a randomized metaheuristic. Such approaches are valid both for the case where the rectangles have fixed orientation and the case where they can be rotated by 90°. We computationally evaluate the performance and the limits of the proposed approaches on a large set of instances, including a number of classical benchmarks from the literature, for both cases above, and for the special case where the items are squares.     

异构云系统中基于智能优化算法的多维资源公平分配

资源分配策略的研究一直是云计算领域研究的热点和难点,针对异构云计算环境下多维资源的公平分配问题,结合基因算法（GA）和差分进化算法（DE）,分别给出了两种兼顾分配公平性和效率的资源分配策略,改进了解矩阵表达式使异构云系统中的主资源公平分配（DRFH）模型转化成为整数线性规划（ILP）模型,并提出了基于最大任务数匹配值（MTM）的初始解产生机制和使不可行解转化为可行解的修正操作,以此提高算法的收敛速度,使其能够快速有效地得到最优分配方案。实验结果表明,基于GA和DE算法的多维资源公平分配策略可以得到近似最优解,在最大化最小主资源份额目标值和资源利用率方面明显优于Best-Fit DRFH和Distributed-DRFH,而且针对不同任务类型的资源需求,具有较强的自适应能力。     

Improving the efficiency of inductive logic programming systems

Inductive logic programming (ILP) is a sub‐field of machine learning that provides an excellent framework for multi‐relational data mining applications. The advantages of ILP have been successfully demonstrated in complex and relevant industrial and scientific problems. However, to produce valuable models, ILP systems often require long running times and large amounts of memory. In this paper we address fundamental issues that have direct impact on the efficiency of ILP systems. Namely, we discuss how improvements in the indexing mechanisms of an underlying logic programming system benefit ILP performance. Furthermore, we propose novel data structures to reduce memory requirements and we suggest a new lazy evaluation technique to search the hypothesis space more efficiently. These proposals have been implemented in the April ILP system and evaluated using several well‐known data sets. The results observed show significant improvements in running time without compromising the accuracy of the models generated. Indeed, the combined techniques achieve several order of magnitudes speedup in some data sets. Moreover, memory requirements are reduced in nearly half of the data sets. Copyright © 2008 John Wiley & Sons, Ltd.     

Multi-mode renewable resource-constrained allocation in PERT networks

This paper presents a hybrid metaheuristic algorithm (HMA) for Multi-Mode Resource-Constrained Project Scheduling Problem (MRCPSP) in PERT networks. A PERT-type project, where activities require resources of various types with random duration, is considered. Each activity can be accomplished in one of several execution modes and each execution mode represents an alternative combination of resource requirements of the activity and its duration. The problem is to minimize the regular criterion namely project's makespan by obtaining an optimal schedule and also the amount of different resources assigned to each activity. The resource project scheduling model is strongly NP-hard, therefore a metaheuristic algorithm is suggested namely HMA. In order to validate the performance of new hybrid metaheuristic algorithm, solutions are compared with optimal solutions for small networks. Also the efficiency of the proposed algorithm, for real world problems, in terms of solution quality and CPU time, is compared to one of the well-known metaheuristic algorithms, namely Genetic Algorithm of Hartmann (GAH). The computational results reveal that the proposed method provides appropriate results for small networks and real world problems.     

软件定义网络中基于网络切片和ILP模型的路由方案

针对软件定义网络(SDN)中数据层的路由优化问题,提出一种基于网络切片和 整数线性规划(ILP) 多约束优化的路由方案。首先,根据多租户业务的链路需求,基于Kruskal算法对数据层中的链路资源进行网络切片,尽可能形成相互隔离的租户子网络。然后,在考虑链路约束和租户业务的服务质量(QoS)约束下, 以最小化传输延迟为目标, 构建一个ILP整数线性规划(ILP)路由优化模型,并获得最佳的路由方案。仿真结果表明,所获得的路由方案具有较少的共享链路,有效降低了链路拥塞和传输延迟。     

Models for the two‐dimensional rectangular single large placement problem with guillotine cuts and constrained pattern

In this paper, we address the constrained two‐dimensional rectangular guillotine single large placement problem (2D_R_CG_SLOPP). This problem involves cutting a rectangular object to produce smaller rectangular items from orthogonal guillotine cuts. In addition, there is an upper limit on the number of copies that can be produced of each item type. To model this problem, we propose a new pseudopolynomial integer nonlinear programming (INLP) formulation and obtain an equivalent integer linear programming (ILP) formulation from it. Additionally, we developed a procedure to reduce the numbers of variables and constraints of the integer linear programming (ILP) formulation, without loss of optimality. From the ILP formulation, we derive two new pseudopolynomial models for particular cases of the 2D_R_CG_SLOPP, which consider only two‐staged or one‐group patterns. Finally, as a specific solution method for the 2D_R_CG_SLOPP, we apply Benders decomposition to the proposed ILP formulation and develop a branch‐and‐Benders‐cut algorithm. All proposed approaches are evaluated through computational experiments using benchmark instances and compared with other formulations available in the literature. The results show that the new formulations are appropriate in scenarios characterized by few item types that are large with respect to the object's dimensions.     

Variable assignment and instruction scheduling for processor with multi-module memory

Multi-module memory has been employed in high-end digital signal processing system (DSP). It provides high memory bandwidth and low power operating mode for energy savings. However, making full use of these architectural features is a challenging problem for code optimization. In this paper, we propose an integer linear programming (ILP) model to optimize the performance and energy consumption of multi-module memories by solving variable assignment, instruction scheduling and operating mode setting problems simultaneously. The combined effect of performance and energy saving requirements has been considered as well. Specially, we develop two optimization techniques to improve the computation efficiency of our ILP model. The experimental results show that the optimal performance and energy solution can be achieved within a reasonable amount of time.     

并行任务图的优化调度算法

科学与工程计算中的很多复杂应用问题需要使用科学工作流技术,超算领域中的科学工作流常以并行任务图建模,并行任务图的有效调度对应用的高效执行有重要意义。给出了资源限制条件下并行任务图的调度模型;针对Fork-Join类并行任务图给出了若干最优化调度结论;针对一般并行任务图提出了一种新的调度算法,该算法考虑了数据通信开销对资源分配和调度性能的影响,并对已有的CPA算法在特定情况下进行了改进。通过实验与常用的CPR和CPA算法做比较,验证了提出的新算法能够获得很好的调度效果。本文提出的调度算法和得到的最优调度结论对工作流应用系统的高性能调度功能开发具有借鉴意义。