Solving an Area-Scanning Problem With a Genetic Algorithm
This project was an experiment in using a genetic algorithm to solve a simple area-scanning problem. I built the simulation in JavaScript and used p5.js for visualization, so I could watch how different drone movement paths evolved over time.
The main idea was to generate possible movement sequences for one or more drones and evaluate how well they scanned a grid-based area. Instead of manually designing the best route, I wanted the system to search for better solutions over generations.
Defining the Problem
The task was based on area coverage. A drone starts from a given position, moves through the grid, and tries to scan as much area as possible.
A good solution should not only scan many cells, but also produce a reasonable path. Because of that, I evaluated each solution using multiple criteria instead of only counting scanned area.
The fitness score included:
- How much area each drone scanned
- How much total area was scanned by the full solution
- Whether the drone path had reasonable movement angles
- Whether the drone could return to its starting point
This made the problem more interesting because the algorithm had to balance coverage with path quality.
Representing a Solution
Each population member represented a possible set of movement directions. At the start, I created a population with random movement sequences.
During each generation, the algorithm evaluated every solution and assigned it a fitness score between 0 and 1. Higher-scoring solutions had a better chance of being selected for reproduction.
This made the simulation feel very visual. I could see a messy set of random paths gradually turn into more structured scanning routes over time.
Selection, Crossover, and Mutation
After calculating fitness scores, the algorithm selected parent solutions based on their scores. Better solutions were more likely to be selected, but weaker solutions could still sometimes survive, which helped keep variety in the population.
For crossover, I used a single-point crossover method. Two parent movement sequences were split from one point and recombined to create new children.
Mutation was handled by randomly replacing some movement directions with new random directions. This gave the algorithm a way to explore new paths instead of only reusing the same patterns.
Testing Different Settings
A big part of the project was testing how different genetic algorithm settings changed the results.
I ran multiple experiments with different drone counts, movement amounts, population sizes, mutation rates, and starting positions. The visual output showed the best solution, the best solution of a generation, and the fitness graph over time.
This helped me understand the algorithm better because I could see both the final path and the improvement process.
Population Size
One important result was that population size had a strong effect on solution quality.
When the population was too small, the average population fitness quickly became close to the best individual. At first that sounds good, but it often meant the population lost variety too early and stopped improving.
In one test, a population size of 500 reached a plateau around generation 679 with a fitness score around 0.84. When I repeated the same example with a population size of 5000, the solution kept improving for much longer and reached around 0.94 fitness near generation 1350.
The tradeoff was computation time. Larger populations produced better results, but they also made each generation more expensive to calculate.
Mutation Rate
Mutation was another important setting.
Without mutation, the population eventually stopped changing. Once the solutions became too similar, the algorithm had no good way to discover new movement patterns.
With too much mutation, the opposite problem happened. The changes became too aggressive, so the population could not preserve useful improvements between generations.
The best behavior came from a small mutation rate. In the experiments, a 0.01 mutation rate showed visible improvement in the early generations, while 0 mutation eventually stopped progress and 0.1 mutation was too unstable.
What I Learned
This project helped me understand genetic algorithms in a more practical way. The core idea is simple: generate candidates, score them, combine better candidates, and occasionally mutate them. But the behavior of the system depends heavily on how the solution is represented and how the fitness function is designed.
The project also showed me why visualization is useful for algorithm experiments. Seeing the drone paths and fitness graph made it easier to understand concepts like premature convergence, population diversity, mutation balance, and local optima.
Final Thoughts
This was a small project, but it gave me a clear hands-on understanding of evolutionary search. It connected abstract AI concepts with something I could see and test directly.
Genetik Algoritmayla Alan Tarama Problemini Çözmek
Bu proje, basit bir alan tarama problemini genetik algoritma kullanarak çözmeye yönelik bir çalışmaydı. Simülasyonu JavaScript ile geliştirdim ve görselleştirme için p5.js kullandım. Böylece farklı drone hareket rotalarının nesiller boyunca nasıl geliştiğini doğrudan gözlemleyebildim.
Temel fikir, bir veya daha fazla drone için olası hareket dizileri üretmek ve bu dizilerin grid tabanlı bir alanı ne kadar iyi taradığını değerlendirmekti. En iyi rotayı elle tasarlamak yerine, sistemin nesiller boyunca daha başarılı çözümler aramasını istedim.
Problemi Tanımlamak
Görev, alan tarama problemi üzerine kuruluydu. Bir drone belirli bir konumdan başlıyor, grid üzerinde hareket ediyor ve mümkün olduğunca geniş bir alanı taramaya çalışıyordu.
İyi bir çözüm yalnızca çok sayıda hücreyi taramamalı, aynı zamanda makul bir hareket rotası da oluşturmalıydı. Bu nedenle her çözümü yalnızca taranan alan miktarına göre değil, birden fazla ölçüte göre değerlendirdim.
Uygunluk puanı şu ölçütleri içeriyordu:
- Her dronenun taradığı alan miktarı
- Tüm çözümde taranmış olan toplam alan
- Drone rotasının makul hareket açılarına sahip olup olmadığı
- Dronenun başlangıç noktasına geri dönüp dönemediği
Bu yapı problemi daha ilgi çekici hâle getirdi çünkü algoritmanın tarama miktarıyla rota kalitesi arasında denge kurması gerekiyordu.
Çözümlerin Temsil Edilişi
Popülasyondaki her birey, olası bir hareket yönleri dizisini temsil ediyordu. Başlangıçta rastgele hareket dizilerinden oluşan bir popülasyon oluşturdum.
Her nesilde algoritma tüm çözümleri değerlendiriyor ve her birine 0 ile 1 arasında bir uygunluk puanı veriyordu. Daha yüksek puan alan çözümlerin üreme için seçilme olasılığı da daha yüksek oluyordu.
Bu durum simülasyonu oldukça görsel hale getiriyordu. Başlangıçtaki dağınık ve rastgele rotaların zamanla daha düzenli tarama yollarına dönüştüğünü izleyebiliyordum.
Seçilim, Çaprazlama ve Mutasyon
Uygunluk puanları hesaplandıktan sonra algoritma, puanlarına göre ebeveyn çözümleri seçiyordu. Daha başarılı çözümler daha yüksek olasılıkla seçiliyor, ancak daha zayıf çözümler de zaman zaman hayatta kalabiliyordu. Bu durum popülasyon içindeki çeşitliliğin korunmasına yardımcı oluyordu.
Çaprazlama için tek noktalı çaprazlama yöntemini kullandım. İki ebeveynin hareket dizileri belirli bir noktadan ayrılıyor ve yeni çocuk çözümler oluşturacak şekilde birleştiriliyordu.
Mutasyon sırasında ise bazı hareket yönleri rastgele yeni yönlerle değiştiriliyordu. Böylece algoritma yalnızca mevcut örüntüleri tekrar etmek yerine yeni rotalar keşfedebiliyordu.
Farklı Ayarları Test Etmek
Projenin önemli bölümlerinden biri, farklı genetik algoritma ayarlarının sonuçları nasıl değiştirdiğini incelemekti.
Drone sayısı, hareket miktarı, popülasyon büyüklüğü, mutasyon oranı ve başlangıç konumu gibi değişkenlerle farklı deneyler gerçekleştirdim. Görsel çıktı; bulunan en iyi çözümü, mevcut neslin en iyi çözümünü ve zaman içindeki uygunluk grafiğini gösteriyordu.
Bu sayede yalnızca nihai rotayı değil, iyileşme sürecini de gözlemleyebildiğim için algoritmanın çalışma mantığını daha iyi anlayabildim.
Popülasyon Büyüklüğü
Önemli sonuçlardan biri, popülasyon büyüklüğünün çözüm kalitesi üzerinde güçlü bir etkisi olduğuydu.
Popülasyon çok küçük olduğunda ortalama uygunluk değeri kısa sürede en iyi bireyin puanına yaklaşıyordu. Bu ilk bakışta olumlu görünse de genellikle popülasyonun çeşitliliğini çok erken kaybettiği ve gelişimin durduğu anlamına geliyordu.
Bir deneyde 500 bireyden oluşan popülasyon, yaklaşık 679. nesilde 0,84 civarında bir uygunluk değerinde plato yaptı. Aynı örneği 5000 bireylik bir popülasyonla tekrarladığımda çözüm çok daha uzun süre gelişmeye devam etti ve yaklaşık 1350. nesilde 0,94 civarında bir uygunluk değerine ulaştı.
Bunun karşılığında hesaplama süresi arttı. Daha büyük popülasyonlar daha iyi sonuçlar üretiyor, ancak her neslin hesaplanmasını da daha maliyetli hâle getiriyordu.
Mutasyon Oranı
Mutasyon oranı da önemli bir ayardı.
Mutasyon olmadığında popülasyon bir süre sonra değişmeyi bırakıyordu. Çözümler birbirine fazla benzediğinde algoritmanın yeni hareket örüntüleri keşfetmesini sağlayacak etkili bir mekanizma kalmıyordu.
Mutasyon oranı fazla yüksek olduğunda ise ters problem ortaya çıkıyordu. Değişiklikler fazla agresif olduğu için popülasyon, nesiller boyunca elde ettiği yararlı gelişmeleri koruyamıyordu.
En iyi davranışı düşük bir mutasyon oranında gözlemledim. Yaptığım deneylerde 0,01 mutasyon oranı ilk nesillerde belirgin bir gelişim gösterirken, 0 mutasyon bir noktadan sonra ilerlemeyi durdurdu ve 0,1 mutasyon oranı fazla kararsız sonuçlar üretti.
Öğrendiklerim
Bu proje, genetik algoritmaları daha uygulamalı biçimde anlamama yardımcı oldu. Temel fikrin aday çözümler üretmek, bunları puanlamak, daha başarılı olanları birleştirmek ve zaman zaman mutasyona uğratmak olduğunu anladım. Ancak sistemin davranışı, çözümün nasıl temsil edildiğine ve uygunluk fonksiyonunun nasıl tasarlandığına büyük ölçüde bağlıydı.
Ayrıca görselleştirmenin algoritma deneylerinde ne kadar faydalı olduğunu gördüm. Drone rotalarını ve uygunluk grafiğini izlemek; erken yakınsama, popülasyon çeşitliliği, mutasyon dengesi ve yerel optimum gibi kavramları anlamayı kolaylaştırdı.
Son Düşünceler
Küçük ölçekli bir proje olmasına rağmen bu çalışma, evrimsel arama konusunda doğrudan deneyim kazanmamı sağladı. Soyut yapay zeka kavramlarını gözlemleyebildiğim ve test edebildiğim somut bir sistemle bir araya getirdi.