Nature-Inspired Algorithms and Applied Optimization

Nature-inspired algorithms are a class of effective tools for solving optimization problems and these algorithms have good properties such as simplicity, flexibility and high efficiency. Despite their popularity in practice, a mathematical framework is yet to be developed to analyze these algorithms theoretically. This work intends to analyze nature-inspired algorithms both qualitatively and quantitatively. We briefly outline the links between self-organization and algorithms, and then analyze algorithms using Markov chain theory, dynamic system and other methods. This can serve as a basis for building a multidisciplinary framework for algorithm analysis.

The No Free Lunch Theorem states that, averaged over all optimisation problems, all non-resampling optimisation algorithms perform equally well. In order to explain the relevance of these theorems for metaheuristic optimisation, we present a detailed discussion on the No Free Lunch Theorem, and various extensions including some which have not appeared in the literature so far. We then show that understanding the No Free Lunch theorems brings us to a position where we can ask about the specific dynamics of an optimisation algorithm, and how those dynamics relate to the properties of optimisation problems.

The cuckoo search (CS) algorithm is a powerful metaheuristic algorithm for solving nonlinear global optimization problems. In this book chapter, we prove the global convergence of this algorithm using a Markov chain framework. By analyzing the state transition process of a population of cuckoos and the homogeneity of the constructed Markov chains, we can show that the constructed stochastic sequences can converge to the optimal state set. We also show that the algorithm structure of cuckoo search satisfies two convergence conditions and thus its global convergence is guaranteed. We then use numerical experiments to demonstrate that cuckoo search can indeed achieve global optimality efficiently.

An evolutionary and discrete variant of the Bat Algorithm (EDBA) is proposed for solving the Vehicle Routing Problem with Time Windows, or VRPTW. The EDBA developed not only presents an improved movement strategy, but it also combines with diverse heuristic operators to deal with this type of complex problems. One of the main new concepts is to unify the search process and the minimization of the routes and total distance in the same operators. This hybridization is achieved by using selective node extractions and subsequent reinsertions. In addition, the new approach analyzes all the routes that compose a solution with the intention of enhancing the diversification ability of the search process. In this study, several variants of the EDBA are shown and tested in order to measure the quality of both metaheuristic algorithms and their operators. The benchmark experiments have been carried out by using the 56 instances that compose the 100 customers Solomon’s benchmark. Two statistical tests have also been carried out so as to analyze the results and draw proper conclusions.

The flower pollination algorithm (FPA) is a nature-inspired algorithm that imitates the pollination behavior of flowering plants. Optimal plant reproduction strategy involves the survival of the fittest as well as the optimal reproduction of plants in terms of numbers. These factors represent the fundamentals of the FPA and are optimization-oriented. Yang developed the FPA in 2012, which has since shown superiority to other metaheuristic algorithms in solving various real-world problems, such as power and energy, signal and image processing, communications, structural design, clustering and feature selection, global function optimization, computer gaming, and wireless sensor networking. Recently, many variants of FPA have been developed by modification, hybridization, and parameter-tuning to cope with the complex nature of optimization problems. Therefore, this chapter provides a comprehensive review for FPA variants from 2012 to present.

Most applications can be modeled using real-valued algebra. Nevertheless, certain problems may be better addressed using different mathematical tools. In this context, complex numbers can be viewed as an alternative to standard algebra, where imaginary numbers allow a broader collection of tools to deal with different types of problems. In addition, hypercomplex numbers extend naïve complex algebra by means of additional imaginary numbers, such as quaternions and octonions. In this work, we will review the literature concerning hypercomplex spaces with an emphasis on the main concepts and fundamentals that build the quaternion and octonion algebra, and why they are interesting approaches that can overcome some potential drawbacks of certain optimization techniques. We show that quaternion- and octonion-based algebra can be used to different optimization problems, allowing smoother fitness landscapes and providing better results than those represented in standard search spaces.

Point cloud approximation by spline models, also called curve and surface reconstruction, is an active research field in computer-aided design and manufacturing (CAD/CAM). Due to the physical and mechanical processes used to obtain the data, the measurements are often affected by noise and other distortions. Obtaining a suitable spline model to reconstruct the underlying shape of the data while maintaining a low design complexity leads to a multivariate and highly non-linear optimization problem, also known to be non-convex and multi-modal. In this work, we propose a method to fit a given point cloud by means of a B-spline curve model. Our approach to solve the optimization problem is based on a powerful thermodynamics-driven metaheuristic known as the Simulated Annealing. We compute the model parameters by combining traditional SA techniques with Lévy flights (random walks based on the Lévy distribution). The ability to perform such a flight allows the algorithm to escape from local minima and energy plateaus, a strong requirement when dealing with highly multi-modal problems. The performance and robustness of our algorithm is tested against three illustrative examples. Our experimental results show that our method is able to reconstruct the underlying shape of the data, even in the presence of noise, with acceptable accuracy and in a completely automated way.

Engineering optimization problems are often solved by using metaheuristic algorithms. Flower pollination algorithm (FPA) is a nature-inspired metaheuristic algorithm and FPA have been used in a variety of engineering problems. In this book chapter, the engineering applications of FPA and its variants are reviewed, and the applications include chemical engineering, civil engineering, energy and power systems, mechanical engineering, electronical and communication engineering, computer science and others. Further research topics are also outlined.

In recent years, the Bat Algorithm (BA) is becoming a standard optimization tool used by scientists and engineers to solve many problems in different engineering fields. One of the most important characteristics of the bat algorithm is its easy, comprehensible structure which simplifies the computer implementation, in addition to its ability to obtain reliable results for low dimensional problems. As the problem complexity increases, several studies pointed out that premature convergence may occur when the algorithm may get trapped at a local optimum. To overcome this without losing the main BA characteristics (simplicity and reliability), the directional echolocation has been introduced to the mainframe of BA to become what is known as the directional Bat Algorithm (dBA). In this paper, we discuss the main features of the dBA and their contributions in improving the exploitation and exploration capabilities of the standard BA. We also analyze the performance of dBA in optimizing unimodal and multimodal functions in addition to a constrained engineering problem. The results are compared with those obtained by BA and also a new competitive improved BA version, namely the Novel Bat Algorithm (NBA). The ANOVA one way analysis has demonstrated the superiority of the directional bat algorithm.

This chapter presents one of the recently proposed bio-inspired optimization methods, namely, flower pollination algorithm (FPA). FPA for its capability to adaptively search a large search space with maybe many local optima has been employed to solve many real problems. FPA is used to handle the feature selection problem in wrapper-based approach where it is used to search the space of feature for an optimal feature set maximizing a given criteria. The used feature selection methodology was applied in classification and regression data sets and was found to be successful. Moreover, FPA was applied to handle the knapsack problem where different data sets with different dimensions were adopted to assess FPA performance. On all the mentioned problems FPA was benchmarked against bat algorithm (BA), genetic algorithm (GA), particle swarm optimization (PSO) and is found to be very competitive.

Firefly algorithm is a nature-inspired optimization algorithm and there have been significant developments since its appearance about 10 years ago. This chapter summarizes the latest developments about the firefly algorithm and its variants as well as their diverse applications. Future research directions are also highlighted.

In solving many “real world” mathematical programming applications, it is often preferable to formulate numerous quantifiably good approaches that provide distinct alternative solutions to the particular problem. This is because decision-making frequently involves complex problems possessing incompatible performance objectives and contain competing design requirements which prove very difficult—if not impossible—to capture and quantify at the time that the supporting decision models are actually formulated. There are invariably unmodelled design issues, not apparent at the time of model construction, which can greatly impact the acceptability of the model’s solutions. Consequently, it can prove preferable to generate numerous alternatives providing contrasting perspectives to the problem. These alternatives should be near-optimal with respect to the known modelled objective(s), but be fundamentally dissimilar from each other in terms of their decision variables. This solution approach has been referred to as modelling to generate-alternatives (MGA). This chapter provides an efficient computational procedure for simultaneously generating multiple different alternatives to an optimal solution using the Firefly Algorithm. The efficacy and efficiency of this approach will be illustrated using a two-dimensional, multimodal optimization test problem.

As a typical model of multicast network, wireless butterfly networks (WBNs) have been studied for modelling the scenario when two source nodes wish to convey data to two destination nodes via an intermediary node namely relay node. In the context of wireless communications, when receiving two data packets from the two source nodes, the relay node can employ either physical-layer network coding or analogue network coding on the combined packet prior to forwarding to the two destination nodes. Evaluating the energy efficiency of these combination approaches, energy-delay trade-off (EDT) is worth to be investigated and the relay placement should be taken into account in the practical network design. This chapter will first investigate the EDT of network coding in the WBNs. Based on the derived EDT, algorithms that optimize the relay position will be developed to either minimize the transmission delay or minimize the energy consumption subject to constraints on power allocation and location of nodes. Furthermore, considering an extended model of the WBN, the relay placement will be studied for a general wireless multicast network with multiple source, relay and destination nodes.

The bat algorithm (BA), a metaheuristic algorithm developed by Xin-She Yang in 2010, has since been modified, and applied to numerous practical optimization problems in engineering. This chapter is a survey of the BA, its variants, some sample real-world optimization applications, and directions for future research.