Application of an Artificial Bee Colony Algorithm for Constrained Optimization Problems

The goal of this project is to develop a stochastic optimization algorithm, Artificial Bee Colony (ABC) for the computer-aided molecular design of novel antibiotics. The design of a novel antibiotic can be formulated as a non-convex, non-linear combinatorics problem, which has a very large search space and fairly inexact constraints, such the use of deterministic methods is inefficient. To think of this problem in a simpler manner, the optimization problem resulting from the CAMD approach can be mathematically represented by the Knapsack Problem (KP), in which the total value of items, each with their own value and weight, in a knapsack is optimized without exceeding the weight constraint. This project focuses on the testing and tuning of the ABC algorithm to find near-optimal solutions of the Knapsack Problem. The 0-1 KP is solved first, followed by the Bounded and Unbounded KPs. The algorithm is written in C++, and was first tested on two sets of 10 and 20 items each before moving on to larger search spaces. By varying only which items were included in or excluded from the knapsack, many potential solutions were found and the best solution was recorded for each instance that it was run. The algorithm consistently found solutions within 95% of the upper bound of the LP relaxation. To represent molecular design more accurately, the algorithm has been expanded and applied to the antibiotics design problem, requiring additional constraints so that multiple chemical and biological properties can be considered. The complete 2D structure of the novel antibiotics is obtained by the use of topological indices as structural descriptors. These initial results show the ABC’s potential not only for antibiotics design, but for many other large scale problems in chemical product optimization as well.