Combining Development and Evolution - Case Study: One Dimensional Bin-packing

Christopher Rajah, Nelishia Pillay

2015

Abstract

The literature highlights the effectiveness of emulating processes from nature to solve complex optimization problems. Two processes in particular that have been investigated are evolution and development. Evolution is achieved by genetic algorithms and the developmental approach was introduced to achieve development. The developmental approach differs from other metaheuristics in that it does not explore the search space applying intensification and diversification to a complete candidate solution. Instead intensification and diversification are performed incrementally, at each step in the process of creating a solution. This is based on an analogy from nature in which a multicellular organism is created incrementally rather than firstly being completely developed and then improved to be fitter. Evolution on the other hand is used to explore the space by applying intensification and diversification to randomly created candidate solutions with the aim of improving the fitness of these candidate solutions and ultimately producing a solution to the problem. Given that in nature once an organism is initially developed its development or growth does not stop at that point but certain cells may continue to grow until a certain point in an organism’s life span, it was felt that the developmental approach terminated prematurely. It was hypothesized that a combination of both these processes, instantiated with development and followed by evolution, would better emulate the processes in nature and would be more effective at exploring the search space. The objective of the research presented in the paper is to test this hypothesis. In terms of search this would mean combining a metaheuristic that applies intensification and diversification incrementally at each step on partial solutions to create initial candidate solutions which are then further explored by a metaheuristic that explores the space of complete candidate solutions. The one-dimensional bin-packing problem was used as a case study to evaluate these ideas. The hybridization of the developmental approach and genetic algorithm was found to perform better than each of these approaches applied separately to solve the problem instances. This study was an initial attempt to test the above hypothesis and has highlighted the potential of this hybridization. Given this future work will apply this approach to other combinatorial optimization problems.

Paper Citation

in Harvard Style

Rajah C. and Pillay N. (2015). Combining Development and Evolution - Case Study: One Dimensional Bin-packing . In Proceedings of the 7th International Joint Conference on Computational Intelligence - Volume 1: ECTA, ISBN 978-989-758-157-1, pages 188-195. DOI: 10.5220/0005592901880195

in Bibtex Style

@conference{ecta15,
author={Christopher Rajah and Nelishia Pillay},
title={Combining Development and Evolution - Case Study: One Dimensional Bin-packing},
booktitle={Proceedings of the 7th International Joint Conference on Computational Intelligence - Volume 1: ECTA,},
year={2015},
pages={188-195},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005592901880195},
isbn={978-989-758-157-1},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 7th International Joint Conference on Computational Intelligence - Volume 1: ECTA,
TI - Combining Development and Evolution - Case Study: One Dimensional Bin-packing
SN - 978-989-758-157-1
AU - Rajah C.
AU - Pillay N.
PY - 2015
SP - 188
EP - 195
DO - 10.5220/0005592901880195