Optimization Problem Solved by a Genetic Algorithm - Wifi Antenna
Suppose you run a small business in your town, let's call your town Smallville, and no unfortunately Clark Kent is absent in this story. Two years ago they found black gold, yes oil and gas, and our countryside town is emerging and growing at an exponential rate. They have expanded the local clinic into a hospital, constructed an elementary school 15 miles north west of the library, the grand opening of the 4 star hotel is set to be in a month and finally the keys for 50 more residential houses are expected to be handed to the owners by the end of the year. If your business is to provide Internet to the locals, you have no choice but to expand your services in order to adapt with the increasing demands.
On a Monday morning you sit back behind the desktop of your office, a couple of Google searches and a few emails later you order a new top of the class antenna that can provide 10 times more data than your current installation. Ten business days later, your brand new X3100 arrives and a few paper works later, Mr Joe the delivery man is set to go his way back to New York. Just as he is climbing into his driver seat, you rush to his vehicle to ask him: Excuse me Sir, but you forgot to give me the manual that indicates where this class A antenna should be installed ? Mr Joe answers you politely: "I only deliver the items my dear and our company only supplies the product, the rest if on you". Seeing Clark Kent does not live in Smallville anymore, you have no choice but to depend on yourself to solve this one!
This short story, as stupid and idiotic as it may seem corresponds to an engineering problem and hopefully by the end of this post, we will solve it. Now let us take a look at the pieces of this puzzle. Let us suppose that my new X3100 is to provide high speed Internet to 5 different locations. Each location is a defined by two properties:
- Coordinates (x,y) (in kilometers)
- Average usage hours per month (in hours)
Now you return back to your office, sit on your warm chair this time scratching your head here and there when it hits you: I can solve this, I've always provided the best quality to my customers and never in 7 years of business have I had one major complaint. I am known to provide the maximum speed where Internet is needed the most. That was always your main objective and you only wish to continue in this fashion.
If I told you that by now, we've solved 50 % of our problem you would probably be anxious to know more. The problem we are dealing with here - the determination of the exact location to install the X3100 is an engineering optimization problem that can formulated as follows:
- Objective Function: maximize the speed of the Internet where the consumption is the highest. This is equivalent to: minimize the sum of the distance weighted by the average usage hours. We can accept this concept by admitting that there is a direct correlation between distance antenna-consumer and the speed (the higher the distance, the slower the speed will be). Since priority is given to the clients with a higher consumption, this protocol has to be included in the objective function. Excuse my drawing skills below, I need to improve my skills in computer drawing softwares (awaiting your suggestions in the comments section), from it we can write the objective function (or fitness function) to our problem.
- Constraints: Yes the town is has plenty of empty space but you the municipality has new regulations. You are only allowed to set your antenna in zone Z1, which happens to be a non habitable forest just north of the public library. Given a reference coordinate system, we are limited to the following area Z1 by:
A general constrained minimization problem can be stated as follows (Rao 2009):
where X is an n-dimensional vector called the design vector (in our case the design vector is composed of the x and y coordinates relative to the location of the antenna on the map), f(X) is termed the objective function (in this example the objective function is the sum of the distances between antenna and consumers weighted by the average consumption of each customer), g(X) and h(X) are know as inequality and equality constraints respectively (the mayor of Smallville was kind to us and only asked to keep the antenna in Z1 described above).
Now how do we solve this constrained optimization problem ? I don't want to review all the optimization techniques in this post, that is not my intention, maybe I will be inspired some other day to post something, but to be as brief as possible, there are two categories:
- traditional mathematical programming techniques. Mostly based on the evaluation of the objective function and its derivatives. They are mostly gradient based approaches.
- modern or untraditional methods. They are based on the behavior of biological, molecular, swarm of insects, neurological systems etc. They are meta-heuristic methods.
Most of the modern techniques have been only developed in recent years and we are beginning to notice that they are emerging as very popular methods for the solution of complex engineering problems. The main advantage is that they only require the function values and not the derivatives (which can be difficult and requires a high computational time to calculate). Between all the modern methods, arguably genetic algorithms are the most famous. Genetic algorithms are based on the principles of natural genetics and natural selection.
Although genetic algorithms were first implemented by Holland, philosophically, they are based on the concepts of biological evolution or Darwin's theory of the survival of the fittest. Genetic algorithms are based on the principles of natural genetics and natural selection. The basic elements of natural genetics are:
As for the process, it is not difficult to comprehend and I will explain in a few lines:
- Initialization: A population of points is formed for the procedure (unlike traditional methods where we choose an initial point). This population can be randomly initiated or it can respect some of our constraints (as to why, the reader is referred to Rao 2009).
- Evaluation: The fitness functions of each chromosome (each vector) of the population is evaluated.
- Sorting: The population is sorted accordingly from the weakest to the strongest fitness (depending whether it is a minimization of a maximization problem). In our case from the weakest to the strongest since f(X) is minimized.
- Selection: The chromosomes that scored the lowest fitness are chosen as the Elites. From the remaining population, children are formed by crossover (marriage of two chromosomes) or by genetic mutation (randomly changing the genes of the chromosomes). The old generation is replaced with the new population to form the next generation.
The processes 2 to 4 are repeated until a stopping criteria is met (usually either we reach the maximum number of generations or a certain convergence tolerance is respected).
This evolutionary process is very simple to program. In fact the main code that I used to solve our antenna X3100 problem is a 76 lines Matlab code. To view, download and use the code click here.
When we run the code that Dr Rafic Younes and I wrote for a population of 500 formed by 10 elites, 130 mutated and the rest (360) are by crossover, we get the following coordinates to set-up our lovely X3100 antenna at the same time respecting the municipality regulation according to Z1:
X = 6.25
Y = 6.39
Now, let us assume the city hall passed a new law that stretches Z1 to form a bigger domain Z2 defined by:
Modifying the upper and lower boundaries, clicking run and a few seconds later we have the exact location of antenna X3100. (X = 5.868 and Y = 2.577).
Now how cool was that ?
Welcome to the world of optimization, welcome to my field of research.