International Journal of Bio-Inspired Computation (37 papers in press)
Earthworm optimization algorithm: a bio-inspired metaheuristic algorithm for global optimization problems
by Gai-Ge Wang, Suash Deb, Leandro Dos Santos Coelho
Abstract: Earthworms are essential animals that aerate the soil with their burrowing action and enrich the soil with their waste nutrients. Inspired by the earthworm contribution in nature, a new kind of bio-inspired metaheuristic algorithm, called earthworm optimization algorithm (EWA), is proposed in this paper. The EWA method is inspired by the two kinds of reproduction (Reproduction 1 and Reproduction 2) of the earthworms in nature. In EWA, the offspring are generated through Reproduction 1 and Reproduction 2 independently, and then, we used weighted sum of all the generated offsprings to get the final earthworm for next generation. Reproduction 1 generates only one offspring by itself that is also special kind of reproduction in nature. Reproduction 2 is to generate one or more than one offspring at one time, and this can successfully done by nine improved crossover operators that are an extended version of classical crossover operator used in DE (differential evolution) and GA (genetic algorithm). With the aim of escaping from local optima and improving the search ability of earthworms, the addition of a Cauchy mutation (CM) is made to the EWA method. In order to show the robustness of EWA method, nine different EWA methods with one, two and three offsprings based on nine improved crossover operators are respectively proposed and they are compared between each other through twenty-two high-dimensional benchmarks. The results show that EWA23 (Uniform crossover operator is used in Reproduction 2) performs the best and is further benchmarked on forty-eight functions and an engineering optimization case. The EWA method is able to find the better function values on most benchmark optimization problems than seven other metaheuristic algorithms.
Keywords: Earthworm optimization algorithm; Evolutionary computation; Benchmark functions; Improved crossover operator.
A Novel Artificial Bee Colony Optimizer with Dynamic Population Size for Multi-level Threshold Image Segmentation
by Lianbo Ma, Xingwei Wang, Hai Shen
Abstract: Existing swarm intelligence (SI) models are usually derived from fixed-population biological system. However, this approach inevitably causes unnecessary computational cost. In addition, the population size of these models is usually hard to be pr-determined appropriately. In this contribution, this paper exploits a general varying-population swarm model (VPSM) with life-cycle foraging rules based on the population growth dynamic principle. This model essentially improves individual-level adaptability and population-level emergence to self-adapt towards an optimal population size. Then, a novel VPSM-based artificial bee colony optimizer is instantiated with orthogonal Latin squares approach and crossover-based social learning strategies. A comprehensive experimental analysis is implemented in which the proposed algorithm is benchmarked against classical bio-mimetic algorithms on CEC2014 test suites. Then, this algorithm is applied for multi-level image segmentation. Computation results show the performance superiority of the proposed algorithm.
Keywords: Artificial bee colony algorithm; Population varying; Image segmentation.
Hybrid Symbiotic Organisms Search Algorithm for Solving 0-1 Knapsack Problem
by Yongquan Zhou
Abstract: We propose a new binary version of hybrid symbiotic organisms search algorithm based on harmony search with greedy strategy for solving 0-1 knapsack problems. A greedy strategy is employed to repair the infeasible solution and optimize the feasible solution. The experiments are carried out in small-scale and large-scale knapsack problem instances. We report on computational experiments which are compared with the results achieved with other state-of-the-art approaches. The results attest the performance of our approach.
Keywords: Knapsack problem; Symbiotic organisms search; Harmony search; Greedy strategy.
Multi-swarm Cooperative Multi-objective Bacterial Foraging Optimization
by Ben Niu, Jing Liu, Lijing Tan
Abstract: his paper proposes a novel multi-objective algorithm which is based on the concept of master-slave swarm, namely Multi-swarm Cooperative Multi-objective Bacterial Foraging Optimization (MCMBFO). In MCMBFO, the multi-swarm cooperative operation which involves several slave-swarms and a master-swarm is developed to accelerate the bacteria to come closer to the true Pareto front. With regard to slave-swarms, each of them evolves collaboratively with others during the step of chemotaxis and reproduction, using information communication mechanism and cross-reproducing approach to enhance the convergence rate respectively. At the same time, bacteria in the master-swarm are all non-dominated individuals selected from slave-swarms. They evolve based on non-dominated sorting approach and crowding distance operation, aiming to improve the accuracy and diversity of solutions. The superiority of MCMBFO is confirmed by simulation experiments using several test problems and performance metrics chosen from prior representative studies.
Keywords: Multi-swarm; Multi-objective; Bacterial Foraging Optimization.
Computer Aided Detection and Classification of Pap smear Cell Images Using Principal Component Analysis
by Sukumar Ponnusamy, Ravi Samikannu
Abstract: Pap smear is a screening methodology employed in cervix cancer detection and diagnosis. The Pap smear images of cervical region are used to detect the abnormality of the cervical cells. In this paper, the computer aided automatic detection and classification method for papsmear cell images are proposed. The cell nucleus is segmented using watershed segmentation methodology and features are extracted from segmented cell nucleus papsmear image. The extracted features are classified using Principal component analysis method. The proposed system classifies the test papsmear cell image into Dysplastic (D), parabasal (P) and Superficial (S) cell images for cervical cancer diagnosis.rn
Keywords: papsmear; cell nucleus; watershed; cervical cancer; features.rn.
Optimization Inspiring from Behavior of Raining in Nature: Droplet Optimization Algorithm
by Hamid Parvin
Abstract: In this paper one of these methods has been proposed called droplet optimization algorithm (DOA). DOA emulates rainfall phenomenon. It employs some special operators to describe the droplet process, including droplet generation, droplet fall, droplet collision, droplet flowing and droplet updating. To compare performance of this algorithm against those of some up-to-dated optimization algorithms, all of the CEC 2005 contest benchmark functions have been employed. The experimental results have proven that DOA superior to all basic optimization algorithms and also some up-to-dated optimization algorithms.
Keywords: Optimizer; DOA; Metaheuristics; General Optimization.
Bit Mask Oriented Genetic Algorithm for Grammatical Inference and Premature Convergence
by Hari Pandey
Abstract: In this paper, a Bit Mask Oriented Genetic Algorithm (BMOGA) is proposed for Grammatical Inference (GI). GI is techniques to infer a context free grammar from a set of positive and negative samples. The BMOGA combines the traditional genetic algorithm, which has a powerful global exploration capability, with a Bit Mask Oriented Data Structure (BMODS) and Boolean based procedure (uses Boolean operators) that can exploit an optimum offspring. The evolutionary operations are performed in two phases: mask-fill for both crossover and mutation and then a Boolean operator based procedure. A vector function is utilized with arguments such as crossover, mutation masks and a couple of parents strings. The arguments crossover and mutation mask helps in replacing various mating rules and therefore no strict rules are to be designed to select an appropriate crossover mechanism. An extensive parameter tuning is done that makes the proposed algorithm more robust, statistically sound, and quickly convergent. The proposed BMOGA is effectively applied over the context free as well as regular languages of varying complexities. The computational experiments show that the proposed BMOGA finds optimal or close-to-optimal grammar with the best fitness value. The Boolean operators introduce diversity in the population that helps in exploring the search space adequately. First, we evaluate the performance of the BMOGA against three algorithms: the genetic algorithm, particle swarm optimization and simulated annealing. Then, the BMOGA is tested with two different offspring generation algorithms: random offspring generation and elite mating pool approach. Statistical tests are conducted that indicate the superiority of the proposed algorithm over others. Overall, a genetic algorithm based tool is developed for the GI, which greatly improves the results, robustness and alleviate premature convergence.
Keywords: Bit-Masking Oriented Data Structure; Context Free Grammar; Genetic Algorithm; Grammar Inference; Learning System.
Labor division in swarm intelligence for allocation problems: A survey
by Renbin Xiao, Yingcong Wang
Abstract: Labor division in swarm intelligence is a kind of swarm behavior widely found in social insects and it provides a flexible task allocation method which is enlightening to solve the allocation problems in dynamic environment. This paper presents a comprehensive survey of labor division in swarm intelligence for allocation problems. At first, labor division in swarm intelligence is introduced and stated from the aspects of phenomena, patterns, characteristics and mechanisms, and then four kinds of models of labor division, viz., group dynamics model, response threshold model, activator-inhibitor model and individual sorting model, are discussed in detail. Based on the contrastive analysis and typical applications of these four models, the allocation problems are divided into continuous allocation problems and discrete allocation problems, and the key points of applying the stimulus-response way and the activation-inhibition way to this two types of problems are analyzed. Furthermore, the research of labor division in swarm intelligence in optimization algorithms and its advantages are discussed. Finally, some perspectives on the development trends of labor division in swarm intelligence are given as the concluding remarks of this paper.
Keywords: swarm intelligence; labor division; task allocation; flexibility; allocation problem.
Hybrid Cuckoo Search Algorithm with Covariance Matrix Adaption Evolution Strategy for Global optimisation Problem
by Xin Zhang, Xiangtao Li, Minghao Yin
Abstract: Cuckoo search algorithm (CS) is an efficient bio-inspired algorithm and has been studied on global optimisation problems extensively. It is expert in solving complicated functions but converges slowly. Another optimisation algorithm, covariance matrix adaption evolution strategy (CMA_ES) can speed up the convergence rate via self-adaptation of the mutation distribution and cumulation of the evolution path, whereas it performs badly in complex functions. Therefore, in this paper, we devise a hybridization of CS and CMA_ES and name it CS_CMA, to enhance the convergence speed and performance for the different optimisation problems. An evolved population is initialised at the beginning of iteration, using the information of previous evolution. During the whole evolution process, self-adaptive parameter adjustments are employed through the successful parameter values. To validate the performance of CS_CMA, comparative experiments are conducted based on seven high-dimensional benchmark functions provided for CEC 2008 and an engineering optimisation problem chosen from CEC 2011, and the computational results demonstrate that CS_CMA outperforms other competitor algorithms.
Keywords: Cuckoo Search; Covariance Matrix Adaptation Evolutionary Strategy; Global optimisation; Self-adaptive method; Cumulation.
Bio-Inspired Reaction Diffusion System Applied to Image Restoration
by Nour Eddine Alaa, Mariam Zirhem
Abstract: In this paper, we propose a new model of nonlinear and anisotropic reaction
diffusion system applied to image restoration and to contrast enhancement. This model is based on a system of partial differential equations of type Fitzhugh-Nagumo. We apply the previous algorithm and the proposed one to realistic images and we confirm the robustness and the performance of our algorithm through a number of experimental results that indicates that it is very efficient for removing noise, enhance image contrast and preserve the edges.
Keywords: Nonlinear anisotropic diffusion; image restoration; Fitzhugh-Nagumo; reaction diffusion system.
Dynamic Data Clustering by Combining Improved Discrete Artificial Bee Colony Algorithm with Fuzzy Logic
by Ehsan Amiri, Mohammad Naderi Dehkordi
Abstract: Data clustering is a method of partitioning data into different groups pursuant to some similarity or dissimilarity measure. Nowadays, several different technics are invented and introduced for data clustering such as heuristics and meta-heuristics. Many clustering algorithms fail when dealing with multi-dimensional data. In this research, we proposed an innovative fuzzy method with improved discrete artificial bee colony (ID is ABC) for data clustering called FID is ABC. The D is ABC is a new version of Artificial Bee Colony (ABC) that first introduced to sort out the uncapacitated facility location (UFLP) problem and improved by the efficient genetic selection to solve dynamic clustering problem. The performance of our algorithm is evaluated and compared with some well-known algorithms. The results show that our algorithm has better performance in comparison with them.
Keywords: Data clustering; Artificial Bee Colony (ABC) Algorithm; dataset; Fuzzy logic; Artificial Intelligence.
TTPA: A Two Tiers PSO Architecture for Dimensionality Reduction
by Shikha Agarwal, Prabhat Ranjan
Abstract: Particle swarm optimization (PSO) is a popular nature inspired computing method due to its fast & accurate performance, exploration & exploitation capability, cognitive & social behaviour and has fewer parameters to adjust. Recently an improved binary PSO (IBPSO) was proposed by Chuang et. al. to avoid getting trapped in local optimum and they have shown that it outperforms all other variants of PSO. Even though many variants of PSO exists independently to improve the performance of PSO, to escape from local optimum and to deal with dimensionality reduction, there still needs an integrated approach to handle it. Hence in this paper two tiers PSO architecture (TTPA) is proposed to find the maximum classification accuracy with minimum number of selected features. The proposed method is used to classify nine benchmarking gene expression data sets. The results show the merits of TTPA.
Keywords: Dimensionality Reduction; Binary Particle Swarm Optimization; FeaturernSelection; Microarray Gene Expression Profile Data.
Symbiotic organisms search algorithm for different economic load dispatch problems
by Dimitrios Gonidakis
Abstract: Economic load dispatch (ELD) is an important topic in engineering management as it is associated with the efficient operation of an electric power generating system. The aim of ELD is to determine the generation dispatch among the thermal units such that the operating cost is minimised. This study presents a novel nature-inspired optimisation method called symbiotic organisms search (SOS) to solve various types of ELD problems. SOS imitates the interaction strategies adopted by organisms to survive in an ecosystem. The proposed method is applied to six different test systems in order to verify its effectiveness and robustness. The simulation results of the proposed SOS algorithm confirm its superiority over other successful optimisation approaches reported in recent literature.
Keywords: symbiotic organisms search; metaheuristics; engineering optimisation; economic load dispatch; valve point loading.
COMPUTER AIDED DIAGNOSIS OF DRUG SENSITIVE PULMONARY TUBERCULOSIS WITH CAVITIES, CONSOLIDATIONS AND NODULAR MANIFESTATIONS ON LUNG CT IMAGES
by Dhalia Sweetlin J, H. Khanna Nehemiah, Kannan Arputharaj
Abstract: In this work, a Computer-aided diagnosis (CAD) system to improve the diagnostic accuracy and consistency in image interpretation of pulmonary tuberculosis is proposed. The lung fields are segmented using region growing and edge reconstruction algorithms. Texture features are extracted from the diseased regions manifested as consolidations, cavitations and nodular opacities. A wrapper approach that combines cuckoo search optimization and one-against-all SVM classifier is used to select optimal feature subset. Cuckoo search algorithm is implemented first using entropy and second without using entropy measure. Training is done with the selected features using one-against-all (SVM) classifier. Among the 98 features extracted from the diseased regions, 47 features are selected with entropy measure giving 92.77% accuracy. When entropy measure is not used, 51 features are selected giving 91.89% accuracy. From the results, it is inferred that selecting appropriate features for training the classifier has an impact on the classifier performance.
Keywords: Computer aided diagnosis; Pulmonary Tuberculosis; Tuberculosis manifestations; Binary Cuckoo Search; one-against-all SVM classification; Drug sensitive TB; Miliary TB; Cavitary TB; Nodular TB.
HYBRID PARTICLE SWARM OPTIMIZATION WITH MUTATION FOR CODE SMELL DETECTION
by Saranya G, H. Khanna Nehemiah, Kannan Arputharaj
Abstract: Code smells are characterized as the structural defects in the software which indicate a poor software design and in turn makes the software hard to maintain. However, detecting and fixing the code smell in the software is a time consuming process, and it is difficult to fix manually. In this paper, an algorithm named as Hybrid Particle Swarm Optimization with Mutation (HPSOM) is used for identification of code smell by automatic generation of rules which represent the combination of metrics and threshold. Moreover, an empirical evaluation to compare HPSOM with other evolutionary approaches such as the Parallel Evolutionary Algorithm (PEA), Genetic Algorithm (GA), Genetic Programming (GP) and Particle Swarm Optimization (PSO) to detect the code smell is done. The analysis shows that the HPSOM algorithm performs better than other approaches when applied on nine open source projects, namely, JfreeChart, GanttProject, ApacheAnt 5.2, ApacheAnt 7.0, Nutch, Log4J, Lucene, Xerces-J and Rhino. HPSOM approach has achieved precision of 94% and recall of 92% on five different types of code smells namely, Blob, Data class, Spaghetti code, Functional decomposition and Feature envy.
Keywords: Search based software engineering; Code smell; Evolutionary algorithms; Software maintenance; Software metrics; Particle Swarm Optimization; Hybrid Particle Swarm Optimization; Cohesion; Coupling; Open source software.
An iterative method to improve the results of Ant-tree algorithm applied to colour quantisation
by María-Luisa Pérez-Delgado
Abstract: Colour quantisation methods attempt to represent a colour image by a palette with fewer colours than the original one. This paper presents a method of this type, based on a previous algorithm called ATCQ (Ant-Tree for Colour Quantisation), which applies artificial ants for colour reduction. An important advantage of the new algorithm is that it does not require sorting the input data. Moreover, it applies an iterative process to increase the quality of the quantised image as iterations proceed. The proposed algorithm gives better results than the original one, and it is competitive with other well-known colour quantisation methods, such as Median-cut, Octree, Neuquant, Variance-based, Binary splitting or Wu\'s methods.
Keywords: colour quantisation; clustering; artificial ants; Ant-tree algorithm; colour image processing.
An Intelligent Traffic Engineering Method for Video Surveillance Systems over Software Defined Networks
by Reza Mohammadi, Reza Javidan
Abstract: Nowadays, Software Defined Network (SDN) is an innovative technology for provisioning Quality of Service (QoS) requirements. SDN network management facilitated using software in which network administrator can perform desired traffic engineering techniques on different applications. Video streaming in video surveillance systems is a critical application which needs QoS requirements such as low packet loss and short delay. These requirements can be satisfied by using traffic engineering techniques over SDNs. In this paper an intelligent traffic engineering technique for a video surveillance system over SDN is proposed. It is based on Constrained Shortest Path (CSP) problem in which the packet loss and delay of video streaming data should be significantly reduced. Due to NP-completeness of the CSP problems, in this paper ant colony optimization algorithm is used to solve it. To the best of our knowledge, this is the first traffic engineering technique used ant colony for video streaming over SDN. Comparisons between the proposed method and prevalent methods such as OSPF routing protocol and LARAC optimization algorithm demonstrated the effectiveness of the proposed method in terms of packet loss, delay and Peak Signal-To-Noise Ratio (PSNR). It was shown that using the proposed method will also ameliorate the traffic engineering for video surveillance systems.
Keywords: Software defined network; ant colony; traffic engineering; video streaming.
Constrained optimisation by solving equivalent dynamic loosely-constrained multiobjective optimisation problem
by Sanyou Zeng, Ruwang Jiao, Changhe Li, Rui Wang
Abstract: A constrained optimisation problem (COP) is solved by solving an equivalent dynamic loosely-constrained multiobjective optimisation problem in this paper. Two strategies are considered. i) An additional objective (constrained-violation objective) is introduced to obtain a twoobjective optimisation problem. This provides a framework for adopting multi-objective techniques to solve the COP. ii) A dynamic constraint boundary is introduced to obtain an equivalent dynamic loosely-constrained multiobjective optimisation problem since a broad boundary is gradually slightly reduced to the original constraint boundary. This suggests that an dynamic constrained multiobjective evolutionary algorithm (DCMOEA) can performs as effective as that of a multiobjective evolutionary algorithm (MOEA) in solving an unconstrained multiobjective optimisation problem. The idea is implemented into three major types of MOEAs, i.e., Pareto ranking based method, decomposition based method, preference-inspired co-evolutionary method. These three instantiations are tested on two sets of benchmark problems. Experimental results show that they are better than or competitive to two state-of-the-art constraint optimizers, especially for the problems with high dimensions.
Keywords: evolutionary algorithm; constrained optimisation; multi-objective optimisation; dynamic optimisation.
Swarm Intelligent Based Congestion Management Using Optimal Rescheduling of Generators
by Surender Reddy Salkuti, Wajid S.A.
Abstract: Congestion Management (CM) refers to the controlling of transmission system such that the power transfer/flow limits are observed. In the restructured electrical system, the challenges of CM for the System Operator (SO) is to maintain the desired level of system reliability and security in the short and long terms, while improving the market/system efficiency. In this paper, the CM problem is tackled by using the centralized optimization i.e., optimal rescheduling of generators, which in turn is solved by using the Swarm intelligent techniques. Here, the CM problem is solved by using the Particle Swarm Optimization (PSO), Fitness Distance Ratio PSO (FDR-PSO) and Fuzzy Adaptive-PSO (FA-PSO). First, the generators are selected based on sensitivity to the over-loaded transmission line, and then these generators are rescheduled to remove the congestion in the transmission line. The suitability and effectiveness of the proposed CM approach is examined on the standard IEEE 30 bus and practical Indian 75 bus systems.
Keywords: Congestion management; Generation rescheduling; Optimal power flow; Generator sensitivity; Evolutionary algorithms; Particle swarm optimization.
Intelligent Swarm Firey Algorithm for the Prediction of China's National Electricity Consumption
by Guangfeng Zhang, Yi Chen
Abstract: China's energy consumption is the world's largest and is still rising, leading to concerns of energy shortage and environmental issues. It is, therefore, necessary to estimate the energy demand and to examine the dynamic nature of the electricity consumption. In this paper, we develop a nonlinear model of energy consumption and utilise a computational intelligence approach, specifically a swarm firefly algorithm with a variable population, to examine China's electricity consumption with historical statistical data from 1980 to 2012. Prediction based on these data using the model and the examination is verified with a bivariate sensitivity analysis, a bias analysis and a forecasting exercise, which all suggest that the national macroeconomic performance, the electricity price, the electricity consumption efficiency and the economic structure are four critical factors determining national electricity consumption. Actuate prediction of the consumption is important as it has explicit policy implications on the electricity sector development and planning for power plants.
Keywords: energy consumption; nonlinear modelling ; swarm firefly algorithm; parameters determination.
A Moving Block Sequence-based Evolutionary Algorithm for Resource-Constrained Project Scheduling Problems
by Xingxing Hao, Jing Liu, Xiaoxiao Yuan, Xianglong Tang, Zhangtao Li
Abstract: In this paper, a new representation for resource-constrained project scheduling problems (RCPSPs), namely moving block sequence (MBS), is proposed. In RCPSPs, every activity has fixed duration and resource demands, therefore, it can be modeled as a rectangle block whose height represents the resource demand and width the duration. Naturally, a project that consists of N activities can be represented as the permutation of N blocks that satisfy the precedence constraints among activities. To decode an MBS to a valid schedule, four move modes are designed according to the situations that how every block can be moved from its initial position to an appropriate location that can minimize the makespan of the project. Based on MBS, the multiagent evolutionary algorithm (MAEA) is used to solve RCPSPs. The proposed algorithm is labeled as MBSMAEA-RCPSP, and by comparing with several state-of-the-art algorithms on benchmark J30, J60, J90 and J120, the effectiveness of MBSMAEA-RCPSP is clearly illustrated.
Keywords: Moving block sequence; Resource-constrained project scheduling problems; Evolutionary algorithms.
Cloud service composition using an inverted ant colony optimization algorithm
by Saied Asghari, Nima Jafari Navimipour
Abstract: In recent years, clouds are becoming an important platform for scientific applications. Service composition is a growing approach that increases the number of applications of cloud computing by reusing attractive services. However, more available approaches focus on producing composite services from a single cloud, limiting the benefits derived from other clouds. Furthermore, in many traditional service composition methods, there is a key problem called load balancing that was inefficient among cloud servers. Therefore, this paper proposes the inverted ant colony optimization (IACO) algorithm, a variation of the basic ant colony optimization (ACO) algorithm, to solve this problem. This method inverts its logic by converting the effect of pheromone on the selected path by ants in order to improve load balancing among cloud servers. In this method, ants begin to traverse the graph from the start node and each ant selects the best node for moving, then other ants may not follow the track travelled by the previous ants. We evaluate the performance of the proposed method in comparison with the ACO, greedy and COM2 algorithms in terms of the obtained optimal cloud composition, load balancing, waiting time, cost and execution time. The results show that the proposed method improves load balancing, reduces waiting time and cost that are the advantages of the proposed method and also increases execution time that is a disadvantage of the proposed method.
Keywords: Cloud computing; Inverted ant colony; Service composition; Load balancing; Optimal cloud composition.
Markov Approach for Quantifying the Software Code Coverage Using Genetic Algorithm in Software Testing
by Sujatha Ramalingam, Boopathi Muthusamy, Senthil Kumar C, Narasimman S, Rajan A
Abstract: Markov Chain approach to quantify the coverage of dd-graph representingrnthe software code using genetic algorithm (GA) is presented in this paper. Initially the ddgraph is captured from the control flow graph. In this technique, test software code coverage is carried out by applying GA through sufficient number of feasible linearly independent paths. These paths have been decided in a software code depending on computational uses and predicate uses. Automatic test cases have been produced for the three mixed data type variables namely, integer, float, Boolean and GA is applied. Transition Probability of the Markov Chain is attained from gcov coverage analysis tool of the initial test suite. Fitness function of GA is measured using path coverage metric; as the product of node coverage and TPM values. Highest fitness value represent the most critical paths among these independent paths with aim to increase testing efficiency of the software code.
Keywords: Software testing; Test adequacy; Cyclomatic complexity; Markov Chain; dd-rngraph; Genetic Algorithm.
Solving many-objective optimization problems by an improved particle swarm optimization approach and a normalized penalty method
by Dexuan Zou, Fei Wang, Nannan Yu, Xiangyong Kong
Abstract: The problem with more than three objectives is commonly known as many-objective optimization problem (MOP), and it has drawn much attention from researchers because of its big potential in the real word. In this paper, a novel modified particle swarm optimization (NMPSO) approach is presented to handle a kind of MOP called many-objective knapsack (MOK) problem. NMPSO relies on the global best particle to guide the search of all particles in each generation, which can enhance the convergence of NMPSO. Furthermore, a randomization-based mutation is adopted to overcome the premature convergence which usually occurs in the late evolutionary optimization process. In addition to many objective functions, MKP consists of several inequality constraints, and all the objective functions should be minimized under the precondition that all the inequality constraints are satisfied. A normalized penalty method (NPM) is devised to reach a compromise between objective functions and inequality constraints, which enables particles to explore solution space more precisely. In summary, the contribution of our work can be summarized in two aspects: (1) A more powerful approach called NMPSO is proposed. (2) A reasonable NPM is devised. Five improved PSOs are used to handle the MOKs with different number of objective functions and dimensions. Experimental results show that NMPSO has higher efficiency than the other four approaches. It uses the lowest computational cost, and achieves the smallest penalty function values for most MKPs.
Keywords: Many-objective optimization problem; Novel modified particle swarm optimization; Many-objective knapsack problem; Randomization-based mutation; Normalized penalty method.
Quantum Inspired Monarch Butterfly Optimization for UCAV Path Planning Navigation Problem
by Jiao-Hong Yi
Abstract: As a complicated high-dimensional optimization problem, path planning navigation problem for Uninhabited Combat Air Vehicles (UCAV) is to obtain a shortest safe flight route with different types of constrains under complicated combating environments. Monarch butterfly optimization (MBO) is a highly promising swarm intelligence algorithm. Since then, though it has successfully solved several challenging problems, MBO may be trapped into local optima sometimes. In order to improve the performance of MBO, quantum computation is firstly incorporated into the basic MBO algorithm, and a new quantum inspired MBO algorithm is then proposed, called QMBO. In QMBO, certain number of the worst butterflies are updated by quantum operators. In this paper, the UCAV path planning navigation problem is modeled into an optimization problem, and then its optimal path can be obtained by the proposed QMBO algorithm. In addition, B-Spline curves are utilized to further smoothen the obtained path and make it more feasible for UCAV. The UCAV path obtained by QMBO is compared with the basic MBO, and the experimental results show that QMBO can find much shorter path than MBO.
Keywords: Unmanned combat air vehicle; Path planning navigation; Monarch butterfly optimization; Quantum computation; B-Spline curve.
A Novel Differential Evolution Approach for Constraint Optimization
by Pooja, Praveena Chaturvedi, Pravesh Kumar, Amit Tomar
Abstract: In the present study, a modified DE framework is proposed, which is a fusion of two modifications in the parent DE: (1) self-adaptive control parameter; (2) single population structure. Both the concepts are used to modify the parent DE that improves the convergence rate without compromising on quality of the solution. While self- adaptive control parameters are used to get a good quality solution, the single population structure helps in faster convergence as reducing the memory and computational efforts. The resultant algorithm, named NDE, found by application of these concepts balances the exploration and exploitation of the parent DE algorithm. The validation of the performance of the proposed NDE algorithm is drawn on a set of benchmark test functions and is compared to several other state-of-the-arts of DE variants. Numerical results pointed out that the proposed NDE algorithm is better than or at least comparable to the parent DE algorithm.
Keywords: Differential Evolution; Control Parameters; Population Structure; Constrained Test Problems.
Multi-objective bat algorithm for mining numerical association rules
by Heraguemi Kamel Eddine, Kamel Nadjet, Drias Habiba
Abstract: Numerical association rule mining problem attracts the attention of
researchers because of the various applications and its importance in our world with
the fast growth of the stored data. ARM is computationally very expensive because the
number of rules grows exponentially as the number of items in the database increases.
Generally, ARM is more complex when we introduce the quality criteria and the usefulness to the user. In this paper deals with the problem of numerical ARM. In which, we propose a new multi-objective meta-heuristic called Multi-Objective Bat algorithm for Association Rules Mining (MOB-ARM). To identify more useful and understandable rules, we introduce four quality measures of association rules: Support, Confidence, Comprehensibility, and Interestingness, in two objective functions. A series of experiments are carried out on several well-known benchmarks in ARM field and the performance of our proposal are evaluated and compared with those of other recently published methods including mono-objective and multi-objective approaches. Also, the paper presents a comparative study with three other methods dealing with multi-objective association rule mining. The obtained results show that our method is competitive with other methods and extract useful and understandable rules.
Keywords: Numerical association rules mining; ARM; Bat algorithm; Multi-objective
optimization; Support; Confidence; comprehensibility; Interestingness.
An Elitist-Flower Pollination based Strategy for Constructing Sequence and Sequence-less T-Way Test Suite
by Abdullah B. Nasser
Abstract: In line with the upcoming of a new field called Search Based Software Engineering (SBSE), many newly developed t-way strategies adopting meta-heuristic algorithms can be seen in the literature for constructing interaction test suite (such as Simulated Annealing (SA), Genetic Algorithm (GA), Ant Colony Optimization Algorithm (ACO), Particle Swarm Optimization (PSO), Harmony Search (HS) and Cuckoo Search (CS)). Although useful, most of the aforementioned t-way strategies have assumed sequence-less interactions amongst input parameters. In the case of reactive system, such an assumption is invalid as some parameter operations (or events) occur in sequence and hence, creating a possibility of bugs triggered by the order (or sequence) of input parameters. If t-way strategies are to be adopted in such a system, there is also a need to support test data generation based on sequence of interactions. In line with such a need, this paper presents a unified strategy based on the new meta-heuristic algorithm, called the Elitist Flower Pollination Algorithm (eFPA), for sequence and sequence-less coverage. Experimental results demonstrate the proposed strategy gives sufficiently competitive results as compared with existing works.
Keywords: T-way Testing; Flower Pollination Algorithm; Event Sequence Testing; Combinatorial Problem; Meta-Heuristics; Optimization Problem.
A New Method to Solve Optimization Problems Via Fixed Point of Firefly Algorithm
by Yu Wenxin, Junjian Wang
Abstract: In this paper, we are going to introduce a novel iteractive method, leading us to find the fixed point of a nonlinear function based on Firefly Algorithm. This new method is able to help us solving nonlinear function more efficiently. In addition, some theorems will obtained by using Firefly Algorithm. At last ,we are going to prove the validity of the proposed technique through some complicated functions as well.
Keywords: Fixed-point; Firefly Algorithm; Nonlinear function; Optimization problems.
An Evolutionary Approach to Schedule Deadline Constrained Bag of Tasks in a Cloud
by Sindhu S, Saswati Mukherjee
Abstract: Bag of Tasks (BoT) is an application model which consists of a large number of independent tasks. In a cloud, computing power is offered as Virtual Machines (VMs) which differ in terms of speed, memory and cost. When such applications are executed on a cloud, an optimal allocation of VMs is needed so that the application executes to completion within the deadline and the cost incurred is minimal. Here the main challenge is to find an optimal trade-off between execution time and execution cost. Genetic Algorithms (GA) are evolutionary algorithms which enable to solve multiobjective problems. This paper proposes a novel Deadline Constrained Bi-Objective Genetic Algorithm based scheduler (DBOGA) to schedule a BoT application onto a cloud. A new fitness fuction is defined. Exploration and exploitation of search space is carried out based on this. An extensive study on the applicability of DBOGA by considering various scenarios is explored.
Keywords: cloud computing;deadline;BoT;makespan;multi-objective optimization;scheduling;virtual machine;genetic algorithm.
EGA-FMC: Enhanced Genetic Algorithm based Fuzzy K - Modes Clustering for Categorical Data
by Medhini Narasimhan, Balaji Balasubramanian, Suryansh Kumar, Nagamma Patil
Abstract: Categorical data clustering is the unsupervised technique of grouping similar objects which have categorical attributes. We propose a Genetic Algorithm based fuzzy K-Modes categorical data clustering algorithm using multi-objective rank based selection with enhanced elitism operation. Compactness of the clusters and inter-cluster separation were chosen as objectives to be optimised. During elitism, in every iteration the best parent chromosomes were identified.The entire population was passed through the selection, crossover and mutation steps. The worst children were then replaced by the best parents. Our method was evaluated on three real-world datasets and resulted in clusters of better quality as compared to current methods with a significant reduction in computation time. Additionally, statistical significance tests were conducted to show the superiority of our approach over other clustering solutions.
Keywords: Genetic Algorithms; Categorical Data Clustering; Multi-Objective Optimisation; Elitism; Fuzzy Clustering.
An Automated Screening System for Vessel Blockage Segmentation in Coronary Angiogram Images Using ANFIS Classifier
by Rajesh Kumar, K. Murugesan
Abstract: Coronary vessel blockage segmentation is the fundamental component which extracts significant features from angiogram images to detect heart disease. This paper proposes an automated method of blockage segmentation from coronary angiogram images using Adaptive Neuro Fuzzy Inference System (ANFIS) classifier. The proposed method consists of preprocessing, feature extraction and classification. The vessels are enhanced using preprocessing technique and then features are extracted from these images which are given to the ANFIS classifier. This classifier classifies the given test coronary image into either normal or abnormal. Further, the blockage is detected and segmented if the proposed system classifies the test image as abnormal. Then, the performance of the proposed system is analyzed in terms of sensitivity, specificity and accuracy with respect to ground truth images. The proposed method achieves 95.9% sensitivity, 99.9% specificity and 99.9% accuracy for blockage vessel pixel detection.
Keywords: Coronary vessel; Angiogram; Feature extraction; ANFIS classifier; Preprocessing.
Preselection via Classification: A Case Study on Global Optimization
by Jinyuan Zhang, Aimin Zhou, Guixu Zhang
Abstract: In evolutionary optimization, the preselection aims to choose promising solutions from a set of candidates before the fitness evaluation and the environmental selection. It is usually based on the approximated fitness values, which are not necessary in many cases because we are usually interested in whether a candidate is good or not instead of how good it is. Actually, the preselection can be regarded as a classification process, i.e., to assign each candidate solution a label (+1 if promising or -1 otherwise). To this end, this paper proposes a classification based preselection (CPS) strategy and applies it to evolutionary optimization. Systematic experiments are conducted to study the performance of CPS, and the experimental results suggest that the CPS strategy can significantly improve the performance of some state-of-the-art evolutionary algorithms on most of the given test instances.
Keywords: Evolutionary algorithm; preselection; classification.
An improved twin support vector machine based on multi-objective cuckoo search for software defect prediction
by Yang Cao, Zhiming Ding, Fei Xue, Xiaotao Rong
Abstract: Recently, software defect prediction (SDP) has drawn much attention as software size becomes larger and consumers hold higher reliability expectations. The premise of SDP is to guide the detection of software bugs and to conserve computational resources. However, in prior research, data imbalances among software defect modules were largely ignored to focus instead on how to improve defect prediction accuracy. In this paper, a novel SDP model based on twin support vector machines (TSVM) and a multi-objective cuckoo search (MOCS) is proposed, called MOCSTSVM. We set the probability of detection and the probability of false alarm as the SDP objectives.
We use TSVM to predict defected modules and employ MOCS to optimize TSVM for this dual-objective optimization problem. To test our approach, we conduct a series of experiments on an open benchmark dataset from the PROMISE. The experimental results demonstrate that our approach achieves good performance compared with other SDP models.
Keywords: Software Defect Prediction; Twin Support Vector Machine; Multi-objective Optimization; Multi-objective Cuckoo Search.
Dynamic Cuckoo Search Algorithm Based on Taguchi Opposition-based Search
by , Juan Li, Yuan-Xiang Li, Sha-sha Tian, Jie Zou
Abstract: The cuckoo search (CS) algorithm is a relatively new, nature-inspired intelligent algorithm that uses a whole updating and evaluation strategy to find solutions for continuous global optimization problems. Despite its efficiency and wide use, CS suffers from premature convergence and poor balance between exploitation and exploration. These issues result from interference phenomena among dimensions that arise when solving multi-dimension function optimization problems. To overcome these issues, we proposed an enhanced CS algorithm called dynamic CS with Taguchi opposition-based search (TOB-DCS) that employed two new strategies: Taguchi opposition-based search and dynamic evaluation. The Taguchi search strategy provided random generalized learning based on opposing relationships to enhance the exploration ability of the algorithm. The dynamic evaluation strategy reduced the number of function evaluations, and accelerated the convergence property. For this research, we conducted experiments on twenty-two classic benchmark functions, including unimodal, multimodal, and shifted test functions. Statistical comparisons of our experimental results showed that the proposed TOB-DCS algorithm made an appropriate trade-off between exploration and exploitation.
Keywords: cuckoo search algorithm; dynamic evaluation; orthogonal opposition-based learning, taguchi opposition-based search.
Period Steady-State Identification for a Non-linear Front Evolution Equation using Genetic Algorithms
by NourEddine Alaa
Abstract: In Molecular Beam Epitaxy, it is known that the planar surface may suffer from a morphological instability in favor to different front pattern formations. In this context, many studies turned their focus to the theoretical and numerical analysis of highly non-linear PDEs which exhibit different scenarios ranging from spacio-temporal chaos to coarsening processes (i. e., an emerging pattern whose typical length scale with time). In this work our attention is addressed toward the study of a highly non-linear front evolution equation proposed by Z. Csahok and al. (1999) where the unknowns are the periodic steady states which play a major role in investigating the coarsening dynamics. Therefore the classical methods of Newton or a fixed point type are not suitable in this situation. To overcome this problem, we develop in this paper a new approach based on heuristic methods such as genetic algorithms in order to compute the unknowns.
Keywords: Front Evolution; Period Identification; Steady States; Stationary Configuration; Coarsening dynamics; Non-linear PDEs; Molecular Beam Epitaxy; Genetic Algorithms.
ABC_DE_FP: A Novel Hybrid Algorithm for Complex Continuous Optimization Problems
by Parul Agarwal, Shikha Mehta
Abstract: Artificial bee colony algorithm (ABC) evolved as one of the efficient swarm intelligence based algorithm in solving various global optimization problems. Though many variants of ABC have evolved, still algorithm depicts poor convergence rate in many situations. Therefore, maintaining balance between intensification and diversification of the algorithm still needs attention. In this context, a novel hybrid ABC algorithm has been developed by integrating FPA and DE in original ABC algorithm. To assess the efficacy of proposed hybrid algorithm, it is primarily compared with contemporary ABC variants such as GABC, IABC and AABC over simple benchmark problems. Thereafter, it is compared with original ABC, FPA, hybrid of ABC_FP, ABC_DE and ABC_SN over complex problems of CEC2014 for up to 100 dimensions. Results reveal that proposed algorithm outperforms its counterparts in terms of minimum error value attained and convergence speed for majority of global numerical optimization functions.
Keywords: Artificial bee colony algorithm; CEC 2014 benchmark functions; nature inspired algorithms; flower pollination algorithm; differential evolution; convergence speed