Inspyred: solving optimization problems with Python

A gentle introduction for bio-inspired algorithms in Python

Inspyred is a Python library that provides bio-inspired algorithms in a simple and easy-to-use way. This guide will help you use and understand it to solve optimization problems by approaching the Particle Swarm Optimization algorithm. The project developed on this guide is available at Github.

1. What is an optimization problem?

According to U. Pahne et al. (1998) an optimization problem is formulated by defining a fitness function with a number of parameters as the variables. The purpose of optimization is to find the best possible solution to a given problem.

Bringing to the real world, let’s imagine that we have a bakery and limited ingredients. There are two possible products to bake: cookies (C) and waffles (W). We sell cookies for $3.50 and waffles for $5.20. Which one is the best to bake in order to get the higher revenue (considering that we will sell everything)?

The most intuitive though is to use all our ingredients to bake waffles, once it is the most expensive one. But this question becomes harder when each of the products uses a different amount of ingredients. In this scenario, we have an optimization problem. Our ingredients are flour (F), eggs (E), oil (O), and sugar (S). The available amount for each one of them and the consumption per product are:

2. Modeling the problem

With all this information, we can start modeling the problem. The first step is to elaborate on the fitness function. Basically, the problem is to find the amount of C and W that multiplied by its prices will give us the highest revenue. The function that represents the revenue can be described as follows:

• Revenue = C*3.50 + W*5.20

Now we can seek values for C and W that will result in the highest revenue possible. However, we need to follow some constraints, and this is the next step of our modeling. As we have seen before, there are limited ingredients, so it is necessary to assume the following constraints:

The amount of flour available is 1750, so the combination of cookies and waffles cannot use more than this. The same goes for all other ingredients:

• F: 10*C + 12*W ≤ 1750
• E: 0.3*C + 0.5*W ≤ 55
• O: 0.2*C + 0.2*W ≤ 30
• S: 1.2*C + 1.7*W ≤ 1000

Following the rules we defined, it is possible to guess some values for C and W and see if we can find the combination which results in the highest revenue. Considering the first approach we’ve talked, and choosing one of the products to use all the ingredients, we go for:

Bake 150 cookies (since there is enough oil to do just 150 cookies) or bake 110 waffles (because the amount of eggs is enough to do just 110 waffles).

• 150*3.50 + 0*5.20 = $525 if we bake cookies
• 0*3.50 + 110*5.20 = $572 if we bake waffles

But there is some kind of combination which will result in higher revenue? Maybe some bio-inspired algorithms can help us with this.

3. Bio-inspired optimization algorithms

Photo by Maksim Shutov on Unsplash

Bio-inspired algorithms are algorithms based not only on living beings but on nature itself, with the purpose of obtaining optimal solutions for complex problems (Ashraf Darwish, 2018). There are a lot of bio-inspired algorithms and each one of them can be used to solve a certain problem. There are also a lot of trade-offs when you compare one algorithm to another.

However, it is not the purpose of this article to explain how bio-inspired algorithms work (maybe in the next time). But if you are interested in this matter, the following survey can help you a lot.

A Survey of Bio inspired Optimization Algorithms | Semantic Scholar

The bakery problem we are approaching here is not quite complex enough to need a powerful bio-inspired optimization algorithm. But for didactic reasons, we will keep it as our example.

4. Inspyred

According to Inspyred Github page:

“inspyred is a free, open source framework for creating biologically-inspired computational intelligence algorithms in Python, including evolutionary computation, swarm intelligence, and immunocomputing. Additionally, inspyred provides easy-to-use canonical versions of many bio-inspired algorithms for users who do not need much customization.”

I’ve been using inspyred for several months and the description above is really coherent. Also, just like the most Python libraries, it is easy to install and get started.

Installation

The code is available on Github, so you can clone and run it by yourself, but there is also a version available at PyPI. If you have PyPI installed, run the following code on cmd/terminal. If everything goes fine, you should be able to import the library in Python.

pip install inspyred

We’ll also use numpy library. If you don’t have numpy, run:

pip install numpy

Algorithm selection

Now we need to decide which bio-inspired algorithm will be used to solve our problem. Like I mentioned before, there are a bunch of them, each one with its advantages and disadvantages. In this guide, we’ll be using Particle Swarm Optimization for two main reasons: it has a simple concept and it’s “fast” (K. Y. Lee and J. Park, 2006).

Basically, the Particle Swarm Optimization (PSO) algorithm is inspired in cooperation and social behavior principles. The swarm is composed by particles (or individuals), which represents a possible solution for the problem. All particles start in a random position in the search space and walk looking for better solutions (based on the fitness function). During the iterations, particles also communicate with each other in order to know about the best solutions found.

The GIF below shows PSO working to find the minimum of a function in a search space with a lot of peaks and valleys. Observing the colors on the right side, we can conclude that this execution found the global optimum (best possible solution) in this search space. But it won’t always be like this. In larger search spaces, find the global optimum can be really time-consuming or even unnecessary. Perhaps other valleys can solve our problem, even if they are not the best ones. These solutions can be called “local optimum”.

By Wikimedia Commons

For the bakery problem, we hope to find the global optimum, once it is a really simple function with a small search space. So let’s start our code to solve the bakery problem.

Problem inputs

The first thing we need to code is the inputs of our problem. Instead of hardcoding everything, we’ll use data structures to make it generic. This way, our solution will work not just for bakeries with cookies and waffles, but for any place that could have the same problem.

So the information we have are:

• Ingredients availability
• Products price
• Products ingredient consumption

The ingredients availability do not need to have descriptive values, we just need to know how much is available, so a simple numpy array can be used. However, each of the products has singular information about price and consumption, so we need a key for them. In this case, a Python dictionary could be useful.

We should use a tuple to store price and consumption in the same dictionary, but we’ll separate them so we don’t need to play with too many indexes.

Problem modeling

With the data in our hands, we need to code the two functions Inspyred requires: generator and evaluator. Those two functions will be used by Inspyred algorithms, not by us. We’ll use a class to represent our problem, so we first need to code our constructor.

Besides the information about products and ingredients, let’s create another four attributes. The “maximize” attribute informs PSO if we are looking for the highest (True) or lowest (False) possible value in the fitness function. In our case, we are trying to find the highest revenue, so let’s assign True for it. The other attributes will be discussed below.

Generator

With the constructor done, let’s code the “generator” function. The generator is responsible for generating each particle of our population. This will happen at the beginning of execution. The function needs to return a single particle. A particle is a solution, so for the bakery problem a solution is the amount of C and W, which can be represented by a list:

particle = [C, W]

This way, we need to create a function that will generate random values for C and W. A good exercise here is to think about boundaries, and this will explain the bounder attribute in our constructor. Looking at the initial data we have, it is possible to bake -1,000 cookies? 50,000 waffles? No. So we don’t need to let PSO waste execution time figuring out this. That’s why we’ll put boundaries.

If we divide product consumption by available ingredients, we’ll know for each ingredient the maximum amount of cookies/waffles we can have. Taking the cookie as an example, we have:

Available Ingredients: [1750, 55, 30, 1000]
Cookie consumption: [10, 0.3, 0.2, 1.2]
Max amount per ingredient: [175, 183.33, 150, 833.33]

So we can see that the third ingredient (oil) limits the maximum amount of cookies at 150. It is not possible to bake 833 cookies, because we just have oil enough to bake 150. The code that represents the search for this upper limit is:

numpy.min(available_ingredients/product_consumption)

The lower limit will be 0 for all products, once it’s not possible to bake a negative amount. Thus, we’ll inform PSO that it’s not necessary to waste time looking for solutions where C > 150 or C < 0 because it will never work. The same goes for waffles. The good thing is that Inspyred does this automatically, we just need to specify the boundaries for each product, and that’s what the “bounder” attribute is for. However, while creating the random initial population of particles we need to respect these boundaries too, so we generate a random number between the lower limit and the upper limit of each product. The code below will generate a single particle, having a random amount for each product (respecting the boundaries for it). This function is what Inspyred uses for generating the population.

The generator function needs to have two arguments. Random is the instance that generates all random numbers. Args is a dictionary that contains information about PSO parameters. The function’s return needs to be a list, which represents a single particle and its characteristics.

Evaluator

The “evaluator” function will be used to test how good to solve the problem each particle of the population is (at each iteration). The question here is, how can we measure this? That’s the challenge of optimization. We already answered this question some sections above. For this problem, the equation is quite simple. Our purpose is to know the highest possible revenue, so the formula to calculate the revenue can be described as below:

Where i is a certain product, n is the number of products of the problem, ai is the amount of the product i and pi the price of the product i. So the fitness of each particle is calculated by its revenue.

So let’s see if this fitness function will work as expected. Once we defined the boundaries for both products, PSO will walk through the search-space and look for the best solution. C can assume values from 0 to 150 and W from 0 to 110. Let’s imagine some scenarios.

• C = 50 / W = 30 (Fitness: 331)
• C = 40 / W = 70 (Fitness: 504)
• C = 150 / W = 110 (Fitness: 1097)

The revenue calculation is right and the best solution in this scenario is the third one, but it is possible to bake 150 cookies and 110 waffles with the amount of ingredient we have? Of course not. So it’s necessary to modify the fitness function to take into consideration the ingredient usage. This way, we’ll add a penalty for all impossible solutions so they have less fitness than viable solutions.

Just like the generator function, the evaluator will follow some rules. The function will also receive two arguments: candidates and args. Args is the same dictionary with information about PSO parameters. Candidates are the list of particles of the population, or the list of actual solutions. Considering that our population has 4 particles, the initial candidates list will be like this:

candidates = [[0, 36] [129, 75] [73, 15] [112, 46]]

where each of the particles was randomly generated by our generator function. The first thing we will do is calculate the revenue for each particle. Taking the second particle as an example, we have:

129*3.5 + 75*5.2 = 841.5

With 129 cookies costing $3.5 and 75 waffles costing $5.2, the revenue will be 841.5. So let’s assign our fitness as 841.5 for now.

Now, we need to check the amount of ingredients being used by each particle. We can measure this by multiplying the product consumption by product amount. We’ll sum the consumption of all products. Therefore, the total consumption per ingredient of the solution will be:

129*[10, 0.3, 0.2, 1.2] = [1290, 38, 25,  154]
 75*[12, 0.5, 0.2, 1.7] = [900 , 37, 15,  127]
                  TOTAL = [2190, 75, 40,  281]

Now, we know how much ingredients this solution is using. Let’s compare with how much we have available and see if it is a valid solution:

AVAILABLE = [1750,  55,  30, 1000]
    TOTAL = [2190,  75,  40,  281]
REMAINDER = [-440, -20, -10,  719]

As the calculation above shows, we don’t have enough ingredients to bake 129 cookies and 75 waffles. This way, we need to penalize the fitness of this particle. We can do this by summing revenue with negative remainders:

REVENUE             = 841.5
NEGATIVE REMAINDERS =  -470
NEW FITNESS         = 371.5

The fitness of this particle is now penalized. However, it was penalized enough to never be the best solution found? We can’t be sure. To guarantee that solutions that use more ingredients than available will never occur, we need to increase this penalty. The penalty increase will be proportional to the amount of products baked. So negative remainders will be multiplied by the total baked products before being summed with revenue. The code that represents the entire evaluation process can be written as follows:

Main

Our class “problem” is finished. The only thing we need to do is instance and run everything. Most parts of the code were already introduced. The focus on the main function will be algorithms parameters.

For instancing PSO, we need to pass the python “Random” instance. The pso.terminator is a class with encapsulated components of generic evolutionary computation, that will be used by the bioinspired algorithms. For PSO, beyond the parameters that refer to the functions we codified, there are another three important ones:

• Population Size: Number of particles to solve the problem. More particles bring more diversity in the population, which implies in the exploration of a broader search-space.
• Max Evaluations: Number of times that evaluator function will be called. Basically, this parameter defines the number of iterations to solve the problem. If you have a population size of 10 and your max_evaluations parameter is set as 100, your population will last for 10 generations.
• Social Rate: As told before, particles talk to each other in order to know about the best solutions. The social_rate concerns about the influence that neighbors will have across the movements of other particles.

At the end of execution, the “evolve” function will return the entire population, having its final values. To get the best solution, we just need to retrieve the max of the final_pop, and to see it, it is necessary to access the “candidate” attribute. The global optimum of this problem is $610 of revenue, which is a result of the combination of 100 cookies and 50 waffles. Remembering that the entire code is available at Github.

That’s it

Hope you learned something, thanks for reading. For any suggestion or question feel free to contact me here or at my Linkedin profile. See you!

References

caiocarneloz/pso-bakery

A parametric finite element environment tuned for numerical optimization — IEEE Journals & Magazine

Application of Particle Swarm Optimization to Economic Dispatch Problem: Advantages and…

Bio-inspired computing: Algorithms review, deep analysis, and the scope of applications

inspyred: Bio-inspired Algorithms in Python — inspyred 1.0 documentation

aarongarrett/inspyred