SYMBIOTIC ORGANISMS SEARCH (SOS)

Authors

Min-Yuan Cheng, myc@mail.ntust.edu.tw

Doddy Prayogo,  doddyprayogo@ymail.com 

Symbiotic Organisms Search (SOS) algorithm is one of very promising recent development in the field of metaheuristic algorithms. The nature-inspired philosophy of SOS algorithm is analogous to the interactive behavior among organisms in nature. Organisms in the real world rarely live in isolation due to dependence on other species for sustenance and survival. In general, organisms develop symbiotic relationships as a strategy to adapt to changes in their environment.

Three cycles of the search are performed mimicking the three symbiotic relationships so-called mutualism phase, commensalism phase, and parasitism phase. By performing this three phases, SOS attempts to move a population, called an ecosystem of possible solutions, to promising areas of the search space during the search for the optimal solution.

Fig. 1. SOS flowchart.

SOS adapts the most common examples of symbiotic relationships found in nature:

1. Mutualism:

This relationship category describes the symbiotic relationship between two different species that benefit mutually from that relationships. Bees fly amongst flowers, gathering nectar to turn into honey. While this activity benefits bees, it also benefits flowers because pollen distribution is a side effect of this process.

Fig. 2. Mutualism between bee and flower.

Both organisms engage in a mutualistic relationship with the goal of increasing mutual survival advantage in the ecosystem. New candidate solutions for X_i and X_j are calculated based on the mutualistic symbiosis between organism X_i and X_j, which is modeled in Equations (1) and (2).

                                                (1)

                                               (2)

                                                                                      (3)

Fig. 3. Visualization of mutualism in the search space.

2. Commensalism:

This relationship category describes the symbiotic relationship between two different species in which one benefits and the other is unaffected or neutral. The remora attaches itself to the shark and eats food leftovers, thus receiving a benefit. The shark is unaffected by remora fish activities and receives minimal, if any, benefit from the relationship.

Fig. 4. Commensalism between remora and shark.

The new candidate solution of X_i is calculated according to the commensal symbiosis between organism X_i and X_j, which is modeled in Equation (4). Following the rules, organism X_i is updated only if its new fitness is better than its pre-interaction fitness.

                                                                                     (4)

Fig. 5. Visualization of commensalism in the search space.

3. Parasitism:

This relationship category describes the symbiotic relationship between two different species in which one benefits and the other is actively harmed. The plasmodium parasite uses its relationship with the anopheles mosquito to pass between human hosts. While the parasite thrives and reproduces inside the human body, its human host suffers malaria and may die as a result.

Fig. 6. Parasitism between anopheles mosquito and human.

Organism X_i is given a role similar to the anopheles mosquito through the creation of an artificial parasite called "Parasite_Vector". Parasite_Vector is created in the search space by duplicating organism X_i, then modifying the randomly selected dimensions using a random number.

Fig. 7. The mutation illustration of the parasite vector (highlighted boxes means that variables were mutated).

Organism X_j is selected randomly from the ecosystem and serves as a host to the parasite vector. Parasite_Vector tries to replace X_j in the ecosystem. Both organisms are then evaluated to measure their fitness. If Parasite_Vector has a better fitness value, it will kill organism X_j and assume its position in the ecosystem. If the fitness value of X_j is better, X_j will have immunity from the parasite and the Parasite_Vector will no longer be able to live in that ecosystem.

Fig. 8. Visualization of parasitism in the search space.

Following is the detailed flowchart of SOS:

SOS Algorithm

1:     iter = 1

2:     Initialize ecosystem / population

3:     repeat

4:             Simulate interaction between organisms through the Mutualism Phase

5:             Simulate interaction between organisms through the Commensalism Phase

6:             Simulate interaction between organisms through the Parasitism Phase

7:             Update the best organism

8:     until iter = max_iter

For more detailed illustrations, please refer to the publications listed above.

Source Code

You may upload and share your source code with different programming languages.

Thus, we can share knowledge with others and learn together.