1. Evolutionary algorithm
Task: Generate a map using the Zen Garden approach
What is Zen Garden? The Zen Garden is an area covered with coarse sand and stationary objects like stones, statues, and structures. The task of a monk is to shape the sand into straight, uninterrupted lines using rakes. These lines can only go horizontally or vertically, never diagonally.
They begin at one side of the garden and continue in a straight line until they reach the opposite side or encounter an obstacle. Outside the garden, the monk can move freely. However, upon encountering an obstacle - a stone or sand that was already raked, he must turn to the other direction. If there's a room to either turn left or right, he can choose the direction. If only one way is open, he has to turn that way. If there is no option to turn, the raking process ends.
The goal is to rake the entire Zen Garden or achieve the maximum coverage.
Solution:
In this approach, we use the following terminology:
Evolution
Collection of Generations
Drawing inspiration from nature, we can simulate the process of evolution. We begin with an initial set of random raking attempts, which forms the starting Generation. As we progress by each generation, the raking attempts will gradually improve.
(this progression of enhancing attempts over time mirrors the way species evolve and adapt in nature)
Generation
Collection of Chromosomes
Generation represents a collection of diverse raking strategies. In the context of Evolution, each generation aims to outperform the previous one by refining its strategies.
(imagine a generation of monks, each experimenting with new ways to rake the garden, contributing their own styles and strategies)
Chromosome
Sequence of Genes
(raking strategy)
Chromosome corresponds to one specific raking strategy.
(It's like a set of instructions for the monk to follow while raking)
Gene
Instruction
(one continuous move)
These instructions are also known as "Genes". Chromosome is formed by an ordered sequence of genes.
(In our context, a gene represents monk's single, continuous movement of the rake on the sand. One raking strategy consists of an ordered sequence of these movements across the garden.)
To create a new generation of raking strategies, we use these 3 tools:
Fitness
The goal is to discover the most effective raking strategy, with the aim to rake the maximum amount of sand. This effectiveness is measured by a score called "Fitness". A higher fitness score indicates more successful raking strategy.
(Think of it like assigning a grade to each monk's raking strategy based on how well it manages to cover the garden.)
Candidate
Within a generation, the best chromosome stands out as the raking strategy with the highest Fitness score. It represents the most successful sequence of raking movements in the garden. This superior solution becomes a "Candidate" that forms the foundation for the next generation.
(Imagine selecting the best monk who serves as a valuable reference for guiding the next generation of monks. Over generations, the strategies progressively improve, similar to how animals evolve over time, inheriting beneficial traits in the process of biological evolution.)
Mutation
To help us discover new ideas, we add a bit of randomness. This is called "Mutation". It involves introducing small, random changes to chromosome by altering some of its genes to diversify the solutions and potentially uncover better ones. In our context, mutation entails altering the order raking movements.
(We can imagine a monk changing the order of movements or making different decisions when encountering obstacles. These slight adjustments help us explore new ideas and avoid getting stuck in one approach.)
Using the tools above to create new generation
Evolution is a cycle of generations, where each generation evaluates all chromosomes using the Fitness function. We select the best candidate from whom we can learn in the next generation. However, the candidates aren't flawless, and some of their moves contain limits that hinder further progressive improvements. To counter this, we employ mutation, which prevents us from being confined to a single approach by encouraging the exploration of new ideas.
Summarization:
This algorithm creates groups (generations) of different raking strategies, where each strategy is like a special raking plan (chromosome). These plans are built from sequence of individual rake movements (genes). The plan's effectiveness in covering the sand is measured by its score (fitness). The best strategy plan (candidate) from each generation progresses to the next round (new generation), serving as the foundation for further improvements. Sometimes, we introduce slight adjustments to the raking plan to explore new ideas (mutation), preventing us from getting stuck in a single approach. This iterative process gradually enhances our sand raking skills (evolution).
Using these AI concepts in the Zen Garden, we can continuously improve our raking strategies over generations of monks. With each iteration, we move closer to the goal of efficiently raking the entire garden, similar to how natural evolution leads to better-adapted species over time.
> 
> 
You can check the implementation on GitHub here.
2. Search algorithms
Task: Find shortest path for visiting set of destinations on map
Let's set aside the Zen Garden problem and consider only the numbers we've obtained from the raking order into the next phase. We will utilize these numbers to define the terrain, indicating the difficulty level of passage for the corresponding locations. Next, we'll randomly position some objects over the map. These include a starting point, a house that needs to be visited first, and fragments of information. The objective is to swiftly collect all the information by identifying the shortest possible path.
Solution:
To find the shortest path, we use these 3 algorithms:
A*
A* uses smart (heuristic) search method, it finds the shortest route to a SPECIFIC destination. We use it to find the route from the starting position to the house.
Dijkstra
Dijkstra uses on straightforward (blind) search method, it finds the shortest route to ALL destinations. We use it separately for each piece of information to find the shortest routes connecting them all.
Held Karp
Knowing the shortest routes between each of the information, we use Held Karp algorithm to find the shortest path that VISITS ALL the information points.
Summarization:
The primary objective is to identify the shortest path for visiting all pieces of information. The process follows a systematic sequence of steps, each aided by specific algorithms.
The journey begins by pinpointing the house as the first destination. The A* algorithm is utilized to determine the shortest route from the starting point to the house. Subsequently, for each piece of information, the Dijkstra's algorithm is applied. It finds that shortest routes to all other information points.
The crux of the process involves the utilization of the Held-Karp algorithm. With the knowledge of the shortest distances between each pair of information points, this algorithm strives to unveil the shortest path that traverses through all the information points.
In the images below, the white node is the starting point, the black node is the house, and blue nodes are information points. Through a harmonious interplay of these algorithms, the process navigates through the map to efficiently visit all information points while minimizing the overall travel distance.
> 
> 
You can check the implementation on GitHub here.
3. Expert Systems
Task: Create a forward-chaining production system
The aim is to develop system that utilizes a forward-chaining production system, streamlining the understanding of fundamental family connections like fathers, uncles, siblings, and more. This system will provide effortless means to explore these fundamental relationships, ensuring a straightforward way to navigate family connections.
Solution:
In this production system, we operate by gathering and processing pieces of information, which we refer to as facts. These facts serve as the foundation upon which we build our knowledge. This process is guided by a set of rules, each consisting of three key components: the condition's name, the condition itself, and an action that is going to expand our knowledge.
The essence of the production system lies in its ability to deduce new insights and knowledge from given facts. As facts accumulate, the system dynamically derives new facts, all driven by the rules we define. This framework streamlines our ability to navigate through the web of information, allowing us to extract insights and solve complex problems.
In our context for example, if we know that Peter is parent of Jano and Vlado, the system figures out that Jano and Vlado are siblings. We can see that in the image on the right.
Here's how to read the information in the image: The first number indicates the order in which we collected the facts. The next number in the parenthesis shows the distance from the previous destination to the one that contains the new fact that we came for. Lastly, there's the text of the collected fact.
You can check the implementation on GitHub here.
Rules and Facts used
Resulting examples
To be successful your content needs to be useful to your readers.
Usage, Implementation - Parameters (GitHub)
Learn - eLearning section