Basic Borg MOEA use for the truly newbies (Part 1/2)

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 were 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:

borgmoea.org

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.Featured image

Featured image

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:

Featured image

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!

Featured image

Go to Basic Borg MOEA use for the truly newbies (Part 2/2)

Advertisements

6 thoughts on “Basic Borg MOEA use for the truly newbies (Part 1/2)

  1. Pingback: Basic Borg MOEA use for the truly newbies (Part 2/2) | Water Programming: A Collaborative Research Blog

  2. Pingback: Random Seed Analysis for the Borg MOEA using DTLZ2, 3 objective instance | Water Programming: A Collaborative Research Blog

  3. Pingback: MOEA diagnostics for a simple test case (Part 1/3) | Water Programming: A Collaborative Research Blog

  4. Pingback: Using Borg in Parallel and Serial with a Python Wrapper – Water Programming: A Collaborative Research Blog

  5. Pingback: Water Programming Blog Guide (Part I) – Water Programming: A Collaborative Research Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s