مدیریت تولید و عملیات (Apr 2018)
Optimization the Problem of Packing Rectangular Shapes by using Imperialist Competitive Algorithm
Abstract
Packing is one of the well-known problems in operation research, especially in production planning. The main objective of studying the packing problem is to reduce the wastes of cutting through optimization of packing of pieces. Packing is a kind of NP-hard problem that the precise methods are not able to solve it. In this paper, in order to achieve an optimal packing of Non-guillotine cutting problems, the meta-heuristic emerging Imperialist Competitive Algorithm was used and the results were compared with the output of the genetic algorithm, which is the typical algorithm in solving packing problems. To achieve better solutions, the parameters of all meta-heuristics were calibrated with Taguchi experiment method. The efficacy of the proposed approach was tested on a set of instances, taken from the literature, and the results of the proposed algorithm were tested statistically by ANOVA. The results of this study showed that the meta-heuristic emerging Imperialist Competitive algorithm is more efficient and faster in solving packing problems. Introduction: Packing problems are problems which are difficult or sometimes impossible to solve exactly. Researchers have provided many different solutions based on heuristic and meta-heuristic to approximately solve these problems. Materials and Methods: Imperialist Competitive Algorithm is a new evolutionaryoptimization method which is inspired by imperialisticcompetition Atashpaz-Gargari (2007). Like other evolutionary algorithms, it startswith an initial population which is called country and isdivided into two types of colonies and imperialists which,together, form empires. Imperialistic competition among theseempires forms the proposed evolutionary algorithm. Duringthis competition, weak empires collapse and powerful onestake possession of their colonies. Imperialistic competitionconverges to a state in which there exists only one empire andcolonies have the same cost function value as the imperialist.The pseudo code of Imperialist competitive algorithm is asfollows: 1) Select some random points on the function and initializethe empires. 2) Move the colonies toward their relevant imperialist (Assimilation). 3) Randomly change the position of some colonies (Revolution). 4) If there is a colony in an empire which has lower costthan the imperialist, exchange the positions of thatcolony and the imperialist. 5) Unite the similar empires. 6) Compute the total cost of all empires. 7) Pick the weakest colony (colonies) from the weakestempires and give it (them) to one of the empires (Imperialistic competition). 8) Eliminate the powerless empires. 9) If stop conditions satisfied, stop, if not go to 2. After dividing all colonies among imperialists and creatingthe initial empires, these colonies start moving toward theirrelevant imperialist state which is based on assimilationpolicy Results and Discussion: In this study, in order to achieve an optimal packing of non-guillotine cutting problems, at first the meta-heuristic algorithm of Imperialist Competitive Algorithm was used. Then the results were compared with the output of the genetic algorithm which is the typical algorithm in solving packing problems. The results showed that ICA had the better fitness function average than GA. Also, ICA needs less number of function evaluations. Therefore ICA is faster than GA in solving permutation packing problems. References Atashpaz-Gargari, E., & Lucas, C. (2007). "Imperialist Competitive Algorithm: An algorithm for optimization inspired by imperialistic competition". IEEE Congress on Evolutionary Computation, 4661-4667 Ebrahimi, S., & Payvandy, P. (2013). "Optimization of the Link Drive Mechanism in a Sewing Machine Using Imperialist Competitive Algorithm". International Journal of Clothing Science and Technology, 26(3), 247 – 260. Bluma, C., & Schmid, V. (2013). "Solving the 2D bin packing problem by means of a hybrid evolutionary algorithm". Procedia Computer Science, 18, 899 – 908.
Keywords
