Using Chemotherapy Science Algorithm (CSA) to Solve the Knapsack Problem

Using Chemotherapy Science Algorithm (CSA) to Solve the Knapsack Problem

Mohammad Hassan Salmani (Sharif University of Technology, Tehran, Islamic Republic of Iran) and Kourosh Eshghi (Sharif University of Technology, Tehran, Islamic Republic of Iran)
Copyright: © 2018 |Pages: 18
DOI: 10.4018/IJEOE.2018010105
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Optimization, which, by definition, can help one find the best solution from all feasible solutions, has sometimes been an interesting and important area for research in science. Solving real and hard optimization problems calls for developing approximate, heuristic, and meta-heuristic algorithms. In this article, a new meta-heuristic algorithm is proposed on the basis of the chemotherapy method to cure cancers – this algorithm mainly searches the infeasible region. As in chemotherapy, this algorithm tries to kill unsatisfactory (especially infeasible) solutions (cancers cells); however, collateral damage is sometimes inevitable – some healthy, innocuous, and good cells might be targeted as well. Also, different conceptual terms including Cell Size, Cell Position, Cell Area, and Random Cells are presented and defined in this article. Furthermore, Chemotherapy Science Algorithm (CSA) and its structure are tested based on benchmark Knapsack Problem. Reported results show the efficiency of the proposed algorithm.
Article Preview

Introduction

Literature Review

Over the past decades, different researchers have proposed exact and approximate methods for addressing optimization problems. Judging from their findings, exact algorithms are only applicable for small-size problems while heuristic approaches should be applied for solving large-scale models and highly non-linear optimization (Neapolitan & Naimipour, 2004) . As a matter of fact, it is argued that meta-heuristic algorithms far surpass the heuristic ones because while the former can have applications for a wide variety of optimization problems, the latter are solely applicable for solving a special class of problems. Among the proposed meta-heuristic algorithms in the literature, the ones inspired by nature with stochastic behavior account for a large percentage of effective algorithms, which can be classified into two groups of population and single-point-based algorithms.

In fact, nature has provided us with some efficient and applicable methods for solving mathematical model problems. Ant Colony Optimization (ACO) (Dorigo, 1992), Simulated Annealing (SA) (Kirkpatrick, Gelatt, & Vecchi, 1983), Genetic Algorithm (GA) (Holland, 1975), and Particle Swarm Optimization (PSO) (Kennedy, 1995) are some of the most well-known nature-inspired approximate optimization algorithms. However, Tabu Search (TS) algorithm, a well-developed algorithm, is not based on natural processes (Glover & McMillan, 1986; Glover, 1986).

In recent years, new algorithms such as Flexible AC Transmission System (FACTS) (Jordehi & Joorabian, 2011), Large-Scale Nonlinear Optimization Algorithm (Martínez & Prudente, 2012), Water Cycle Algorithm (WCA) (Eskandar & Sadollah, 2012), Migrating Birds Optimization (MBO) (Duman, Uysal, & Alkaya, 2012), Mine Blast Algorithm (Ali Sadollah, Eskandar, & Hamdi, 2012), and Three-Term Conjugate Gradient Algorithm (Andrei, 2015) have been presented in the literature. Also, a smart structural algorithm (SSA) based on infeasible region to solve mixed integer problems was proposed in 2017 (Salmani & Eshghi, 2017). Moreover, it is possible to find some studies in literature which focus on proposing a hybrid algorithm as a combination of two well-known meta-heuristic algorithms. In this regard, we can refer to (Roy & G, 2017). In 2017, Salmani and Eshghi proposed CSA algorithm which was based on a health science to solve some of the optimization problem such as Transportation Salesman Problem (TSP) (Salmani & Eshghi, 2017). Salmani and Eshghi (2016) as a conference paper proposed a metaheuristic algorithm which were used to solve a benchmark knapsack problem. Some of the most recent optimization algorithms are shown in Table 1.

Table 1.
List of some meta-heuristic algorithms in recent years
No.YearAlgorithm
12011Shah-Hosseini introduced the Galaxy-based Search Algorithm (GbSA) (Shah-Hosseini, 2011).
22011Tamura and Yasuda designed Spiral Optimization (SO) (Tamura & Yasuda, 2011).
32011Rao et al. presented Teaching-Learning-Based Optimization (TLBO) algorithm (Rao, Savsani, & Vakharia, 2011).
42012Gandomi and Alavi proposed the Krill Herd (KH) Algorithm (Gandomi & Alavi, 2012).
52012Çivicioglu introduced Differential Search Algorithm (DSA) (Civicioglu, 2012).
62013Gandomi et al. introduced Cuckoo Search Algorithm (CSA): A Meta-heuristic Approach to Solving Structural Optimization Problems (Gandomi, Yang, & Alavi, 2013).
72013Gandomi et al. Firefly Algorithm (FA) with Chaos (Gandomi, Yang, Talatahari, & Alavi, 2013).
82014Kaveh and Mahdavi developed Colliding Bodies Optimization (CBO) Algorithm (Kaveh & Mahdavi, 2014).
92014Beheshti and Shamsuddin et al. presented CAPSO: Centripetal accelerated particle swarm optimization (Beheshti & Shamsuddin, 2014).
102014Meng et al. designed Crisscross Optimization Algorithm (COA) (Meng, Chen, Yin, & Chen, 2014).
112015Javidi et al. proposed Lons Motion Algorithm (LMA) (Javidy, Hatamlou, & Mirjalili, 2015).
122015James and Victor introduced A Social Spider Algorithm (SSA) (Yu & Li, 2015).
132016R. Venkata Rao proposed Jaya algorithm as a simple algorithm (Rao, 2016).

In this study a chemotherapy (sometimes called “chemo”)-based algorithm is proposed to solve optimization problems. Chemotherapy uses over 100 powerful chemical drugs to treat cancer in a cyclic and repetitive procedure, which can stop the cancer from spreading, slow its growth, kill cancer cells that may have spread to other parts of the body, relieve symptoms such as pain or blockages caused by the cancer, and cure it (Society, 2013). In chemo, scientists seek to kill cancer cells that divide rapidly where most of the time chemo drugs are put right into the bloodstream or taken as pills and sometimes there is a need to get high doses of chemo to a specific area of the body to travel throughout the body to kill cancer cells. Regional chemotherapy directs the anti-cancer drugs into the part of the body where the cancer is found. In the case of chemo, the primary goal is to get more of the drug to the cancer, while trying to limit the side effects on the whole body.

Our algorithm has close parallels with chemotherapy cancer treatment. In fact, this algorithm searches the infeasible region where infeasible and feasible solutions are the same as cancer and healthy cells, respectively. In addition, as some of the healthy cells get killed during treatment and their number decreases, the number of appropriate feasible solutions that may be lost during the algorithm run is bound to decrease too. Moreover, each iteration of the algorithm is similar to each cycle of treatment and while the patient rests (between each two successive cycles) to recover the killed healthy cells, thus increasing the number of cancer cells, the algorithm generates some other feasible and infeasible solutions to start the next iteration.

This paper is structured as follow. First of all, the main body of algorithm is presented in detail in section 2. Afterward, the computational results based on a sample benchmark problem is proposed. Finally, this study is recapitulated in conclusion.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 7: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 6: 4 Issues (2017)
Volume 5: 4 Issues (2016)
Volume 4: 4 Issues (2015)
Volume 3: 4 Issues (2014)
Volume 2: 4 Issues (2013)
Volume 1: 4 Issues (2012)
View Complete Journal Contents Listing