Homage to PHP Open Source Community and welcome my Genetic Algorithms Library in PHP (yes, PHP)!

Many years ago, I wanted to join the PHP Freelancers club and began searching for global freelance jobs that I could undertake. Honestly, it was my first experience, and receiving any response from a client was extremely difficult. Sending applications randomly was not the best strategy, and it took me a couple of months to discover the secret of securing a freelance job.

After numerous failed applications, I started to review my entire process and then worked hard to build some empathy with the clients. For many years as a developer, I had been sitting behind the curtain, in my comfort zone, simply focusing on my tasks and progressing them. It became clear that I needed to change my mindset to secure a job in the freelance world. The reason I wasn't getting any jobs wasn't that I was a bad developer, or because I failed to sell my skills; it was that I was missing one of the simplest yet most powerful rules in the world: the supply and demand equilibrium.

Basic example of the relationship between supply and demand

As a developer on the supplier side, I was struggling to find a suitable demand. I applied for ALL PHP freelance jobs, sometimes only modifying the cover letter slightly. Clearly, my supply of job applications was very poor. Then, I decided to take a different approach and found a job that required solving an optimization issue using PHP and JQuery (good old days, right?). For this job, the client needed:

A feature allowing users to add sources, warehouses, and destinations of cargo trucks on Google Maps.

The project should also be able to draw the optimal route for deliveries on Google Maps.

For this job, instead of submitting a generic cover letter stating my competencies, I REALLY solved the problem (which took a considerable amount of time) using some pseudo-code and shared ALL my findings with the client, including the design, my thought process, reasons for my choices, etc. My solution involved identifying origins for every route of all trucks, using k-means to cluster these origins, and then assigning destinations to the trucks based on their distances. A day later, the client got back to me, eager to work together.

At the beginning of the project, I didn’t want to reinvent the wheel, so I decided to check if any relevant libraries had already been written and shared on Packagist. Fortunately, I was in luck! I installed a library I found, and it worked like a charm! Within a few days, I had easily built the backend and the UI, as the hardest part had already been solved by someone I had never met before. In the end, the client was satisfied, and I was too, but I also felt a sense of gratitude towards the PHP open source community.

My wife, a teacher at a public school, often tells me about a recurring issue they face every year: scheduling classes and teachers. Each teacher and class has unique constraints that change annually, leading to inevitable schedule revisions at least twice in the first month. Earlier this year, my wife brought up the problem again and asked if I could find a tool to help resolve it. While there are numerous tools available, most of them address very specific issues. The lack of a suitable solution triggered an idea in my mind: to develop a Genetic Algorithm library. Genetic Algorithms are incredibly effective in identifying nearly optimal solutions in a short time. Still feeling indebted to the PHP open-source community since I stopped freelancing, I decided to create this library in PHP. Although there were some existing PHP libraries for Genetic Algorithms, most were outdated, and I was eager for a challenge. My familiarity with Genetic Algorithms was a good start, but I did some additional research and refreshed my knowledge (I've shared the resources at the end).

With the simplest approach, a Genetic Algorithm has this flow:

Build the population (list all possibilities)

Define the fitness function (to check how any possibility is good for the problem)

Iterate all the population unless getting the best fit or reaching the limit

In each iteration:

Pick the best parents from the population (by checking their score from the fitness function)
Crossover them to build better children (each iteration should be better than previous ideally)
Replace the children with their parents in the population (to make the population better)
Mutate new individuals sometimes (depends on how much you want to randomize the possibilities)

I decided to create a simple version for the beginning by allowing developers to write their solutions easily. I started with this design:

Here are the basic descriptions of the classes in the Knapsack problem:

GeneInterface and Chromosome: These are the fundamental classes that hold the essential information. In the context of the knapsack problem, they should store the weight and value of each item.

Individual: This class creates a link between the Chromosome and other classes responsible for actions like mutation or fitness calculation.

CalculatorInterface: This interface is for fitness calculators. Fitness calculators assess how well a chromosome meets the requirements. For the knapsack problem, this means ensuring the total weight of items is below a certain limit, while the total value is as high as possible.

CrossOverInterface: The cross-over process aims to enhance the population. Initially, the best parents are selected. Then, through cross-over, the offspring are expected to surpass their parents in quality. The fitness calculator mentioned earlier is used for these comparisons.

MutatorInterface: In AI, it's common to encounter local maxima as seemingly optimal solutions. To address this, similar to natural processes, it's beneficial to introduce randomness in iterations.

Problem: This class is responsible for managing the iterations mentioned above.

And now I am glad to share the first version of the library: https://github.com/sedatsevgili/Charlie

In this version, you can explore the knapsack function example and construct a basic solution by implementing the interfaces specified in the project's readme. My upcoming plans include:

Developing a web app that solves a practical problem, such as the class scheduling issue mentioned previously.

Creating bridges for Symfony and Laravel to facilitate the integration of this project into PHP applications.

Expanding the capabilities by enhancing the Problem class with more options.

If you are curious about Genetic Algorithms and want to get some basics I recommend these videos:

But if these videos are not enough for you, then I recommend that book: https://www.amazon.com/Hands-Genetic-Algorithms-Python-intelligence/dp/1838557741/