The Truly Newbie Series brings to you Basic Borg MOEA use. Part 1 provides a quick overview of the Borg MOEA, it helps you obtain the Borg MOEA source code and compile it. Part 2 will take you by the hand on a basic Borg MOEA use, demonstrated with the DTLZ2, 3 objective test problem.
If you need basic background on multi-objective evolutionary algorithms, I strongly recommend reading Jon H’s post first.
1. What is the Borg Multiobjective Evolutionary Algorithm (MOEA)?
The Borg MOEA, developed by Dave Hadka and Pat Reed, is an iterative search algorithm for many-objective optimization. Some currently available MOEAs are highly dependent on their search parameters, that is, their crossover, mutation and selection operators, which are usually pre-specified and do not change throughout the run. The Borg MOEA avoids sensitivity to search parameters by assimilating a suite of operators from existing MOEAs and adaptively using them based on their success throughout the search. For instance, if an operator has a large contribution to the archive, it has a larger probability of being selected (the archive is basically where the top solutions are stored). MOEAs also struggle with problems that have multiple false optima, that is, they are looking for the mountain and they get stuck in a hill. The Borg MOEA avoids this problem by checking for progress in the archive over a fixed period of time, if there is no improvement detected, this might be a good indication that the MOEA is stuck in local optima and a new set of solutions are injected to reinvigorate the search. Borg can also shrink or enlarge its population to maintain proportionality to the archive size. If the population size starts becoming smaller than the archive size, then it’s time to bring some new solutions into the mix to keep diversity. In brief, checking for progress, adapting the population size and adding new solutions helps the algorithm to continue progress and prevents it from going around in circles for the entire runtime. Finally, the sorting mechanism in some MOEAs is performed by checking all of the solutions against all of the other solutions, this can be extremely time-consuming and the MOEAs may have trouble sorting when the number of solutions is exceedingly large, this is usually the case when dealing with a large objective count. Alternatively, Borg allows the user to specify the precision for each of the objectives. For instance, if revenue is one of our objectives, we might only care about measuring to the nearest hundred dollars, instead of measuring to the nearest dime. This sorting procedure enhances diversity since it avoids storing solutions that are not significantly different from each other. It also guarantees convergence to the best known set of tradeoffs and avoids wasting time when comparing solutions. In summary, the Borg MOEA is a highly auto-adaptive optimization tool that assimilates characteristics from existing MOEAs while adding several innovative components that help it deal with a broad range of challenging multi-objective problems. (You can probably infer at this point why it gets its scary Star Trek-referenced name).
Note: I did not mean to murder the Borg MOEA with this overly-simplified explanation, please do read the original paper to learn more about its cool features and full details:
Hadka, D., and Reed, P.M. “Borg: An Auto-Adaptive Many-Objective Evolutionary Computing Framework.” Evolutionary Computation, 21(2):231-259, 2013.
2. How to get the Borg MOEA?
The Borg MOEA is freely available for academic use, you can go to the following link:
Next, request access by completing the Get it! section, the providers should contact you within three business days, in my experience, it takes them about 3 business minutes to get back to you. You will receive a Bitbucket invitation by e-mail, which means that you will need to open a bitbucket account first. Accept the invitation, and then you should see the following window. In the left menu, click downloads, once you are in the Downloads folder click Download Repository.
Next, go to your downloads folder, look for the dmh309-serial-borg-moea-eb8f1ca9d731 folder, extract the files and select a destination. In the folder, you should see the following files:
3. Compiling Borg MOEA
To compile the Borg MOEA, you will need a compatible C compiler installed, gcc is highy recommended. You will also need to have access to Linux-like terminal. If you don’t already have access to one, please refer to the terminal basics post for some guidance. Next, navigate the borg folder through your terminal, you can see that a makefile is provided to help build the Borg MOEA code automatically, you just need to type the command make, and the three executables distributed will be generated. In your terminal you can type the ls command to verify that you have the following: borg.exe, dtlz2_advanced.exe and dtlz2_serial.exe where created. Once you have these three executables, this step is completed!