Digitizing Hospitals During The COVID-19 Pandemic

A wave of change is hitting the healthcare systems and will continue to do so after the pandemic. The innovation in digital healthcare is tremendous, but the pace of application has been slow for years, and very few hospital executives have taken it upon themselves to begin a digitization strategy.

Performance of Particle Swarm Optimization in One Max Problem

Particle Swarm Optimization (PSO) is a population-based optimization algorithm that is generally developed by observing the social behavior of bird and fish swarms 🐦🐟 [1]. This optimization algorithm is often a very frequently used algorithm in the literature. In this article, I will explain the use and performance of the PSO (Particle Swarm Optimization) algorithm to solve the One Maximization problem. But first, let’s consolidate the information I have collected for you by learning from different sources so that we can comprehend the logic of the algorithm.

In the development of the PSO algorithm, which is one of the most used methods of metasestical optimization, the ability to adapt to the environment, to search for rich food sources and to escape from predators is based on the approach of information slharing. 🌽 🥗 [2].

Swarm Logic

Particle Swarm Optimization was inspired by the observation that the movements of animals moving in packs, while meeting their basic needs, such as finding food, affect other individuals in the swarm and achieve the purpose of the swarm more easily. Kennedy and Dr. It is an optimization algorithm developed by Eberhart in 1995 [4].

As is often seen in other optimization algorithms, particles tend to follow the best in the PSO algorithm. For this reason, after a while all the particles are clustered in one place looking for the solution [4]. When you run the code of the PSO algorithm, after a while you will observe that the particles are actually clustered somewhere 👀

The particles try to find the best position by going to different positions with velocity change based on this velocity formula. The particle that is in the best position is followed because it is worked with herd logic. A cluster is seen in this way.

Calculation Phase In The Use Of One Max Problem

The One Max problem is a simple optimization problem. The goal of the problem is to maximize the number of those in a workable solution. The formula for the problem is given below. D contained in this formula denotes the size of the problem 🔖

For the maximization problem you see above, the cost function to be used in the PSO algorithm has been determined as Sigmoid. The Sigmoid function controls the values it takes with 0.5 . With this function, the particles have all the particles in the Dimension Sigmoid’den output above 0.5 value is to increase. Thus, output above 0.5 will be equal to 1. When other studies studied on this algorithm in the literature are examined, w, c1 and c2 values in the speed change formula of the particles are taken differently 💡

Sigmoid Function Working Chart [5]
Statistical Results with Wilcoxon

First, the w value is 0.005, c1 value is 0.005 and c2 value is 0.009 . A total of 40 particles are studied in the population. Based on these values, it has been run 30 times for dimensions D=100, 500 and 1000 respectively. The value specified as D indicates the problem size. Accordingly, the following table prints the result values calculated with Wilcoxon 📝

D size of problem: 100, number of iterations : 100.000 and total 30 times run
This image has an empty alt attribute; its file name is image-47.png
MeanMedianBest ValueWorst ValueStandard Deviation
0.0031551897084034007 0.0025380204697822194 0.00023797210224091314 0.008994153476226206 0.0020874904616420636
D size of problem: 500, number of iterations : 100.000 and total 30 times run
MeanMedianBest ValueWorst ValueStandard Deviation
0.0024457287103268333 0.002274384447498488 0.0001588232061854383 0.0001588232061854383 0.0016983186907986983
D size of problem: 1000, number of iterations : 100.000 and total 30 times run
MeanMedianBest ValueWorst ValueStandard Deviation
0.0014781328189136006 0.0010733144689043976 7.397751636520865e-05 0.004376988570160589 0.0010840516145429367

Then the w value is 0.4, c1 value is 1.5 and c2 value is 2. A total of 40 particles are studied in the population. Based on these values, it has been run 30 times for dimensions D=100, 500 and 1000 respectively. The value specified as D indicates the problem size. Accordingly, the following table prints the result values calculated with Wilcoxon 📝

D size of problem: 100, number of iterations : 100.000 and total 30 times run
MeanMedianBest ValueWorst ValueStandard Deviation
0.10290449068126414 0.06354761821949564 0.0014967006497636770.44050232006176950.11308392205322863
D size of problem: 500, number of iterations : 100.000 and total 30 times run
MeanMedianBest ValueWorst ValueStandard Deviation
0.110903396496039350.07350043038100676 0.00101170646510823080.51253800338024250.11343766955639699
D size of problem: 1000, number of iterations : 100.000 and total 30 times run
MeanMedianBest ValueWorst ValueStandard Deviation
0.1276016324307818 0.0487016911393234750.00058108724675987040.70159657090303230.15191292927119768

🕵 The mean, median and standard deviation increase as the values w, c1, c2 are increased compared to these values. The fact that the standard deviation is large also means that particles in the series i.e. population deviate from the mean. With the above preferred values, the best result is that the minimum value is reached more easily.

🏋 It was observed that when the w value in the first values is 0.005, c1 value is 0.005 and c2 value is 0.009, the desired result is more easily achieved. D = 100, 500 and 1000. when increased to size the value of the best position has been seen to get smaller and smaller, and this is a desirable situation.

NOTE 🌠

The best_globalbest value for the PSO algorithm is held in a numpy array and then the following values are reached by applying the Wilcoxon statistic.

📌If you want to review the code, I’ll publish it to you as a GitHub repo. I wish you good work 🐞

REFERENCES

[1] M. Yasin OZSAGLAM, Mehmet CUNKAS, particle swarm optimization algorithm for solving optimization problems, Polytechnic, Volume:11 Issue: 4 p.299-305, 2008.

[2] Fırat University, BMÜ-579 Metasestical methods, particle swarm optimization.

[3] Pablo J. Villacorta, Swarm Intelligence Metaheuristics, part 2: Particle Swarm Optimization, https://www.stratio.com/blog/swarm-intelligence-metaheuristics-part-2-particle-swarm-optimization/.

[4] Muhammad Pektas, April 2019, taken from Particle swarm optimization (PSO) Medium article.

[5] https://en.wikipedia.org/wiki/Sigmoid_function retrieved from address.

Parçacık Sürü Optimizasyonunun(PSO) OneMax Problemindeki Performansı

Parçacık Sürü Optimizasyonu (PSO), genellikle kuş ve balık sürülerinin sosyal davranışları gözlemleyerek geliştirilen popülasyon temelli bir optimizasyon algoritmasıdır 🐦🐟 [1]. 

Bu optimizasyon algoritması genellikle literatürde çok sık kullanılan bir algoritmadır.

Bu yazımda sizlere One Maximization probleminin çözülmesinde PSO (Particle Swarm Optimization) algoritmasının kullanılışını ve performansını açıklayacağım.

Ama öncelikle sizler için topladığım farklı kaynaklardan bilgileri öğrenerek pekiştirelim ki algoritma mantığını kavrayabilelim.

Metasezgisel optimizasyon yöntemlerinden olan PSO algoritmasının geliştirilmesinde en çok kullanılan kuş sürüleri ele alındığında bilgi paylaşımı yaklaşımı kullanılarak çevreye adapte olabilme, zengin yiyecek kaynağı arama ve avcılardan kaçabilme yetenekleri baz alınmıştır 🌽🥗 [2].

sürü mantığıyla uçan kuş resmi

Sürü Mantığı [3]

Parçacık Sürü Optimizasyonu, sürü halinde hareket eden hayvanların yiyecek bulmak gibi temel ihtiyaçlarını giderirken sergiledikleri hareketlerin, sürüdeki diğer bireyleri etkilediğinin ve sürünün amacına daha kolay ulaştığının gözlemlenmesinden esinlenilerek Dr. Kennedy ve Dr. Eberhart tarafından 1995 yılında geliştirilmiş bir optimizasyon algoritmasıdır [4].

Diğer optimizasyon algoritmalarında da genellikle görüldüğü gibi PSO algoritmasında da parçacıklar en iyiyi takip etme eğiliminde olmaktadır. Bu sebepten dolayı, bir süre sonra tüm parçacıklar bir yerde kümelenmiş halde çözümü arıyor olarak bulunmaktadır [4].

PSO algoritmasının kodunu çalıştırdığınızda ise bir süre sonra parçacıkların gerçekten bir yerde kümelenmiş olduğunu gözlemleyeceksiniz 👀

Parçacıklar, bu hız formülüne dayanarak hız değişimi ile farklı konumlara giderek en iyi konumu bulmaya çalışmaktadır. Sürü mantığı ile çalışıldığı için en iyi pozisyonda olan parçacık takip edilmektedir. Bu şekilde bir kümelenme görülmektedir.

One Max Probleminin Kullanımındaki Hesaplama Aşaması

One Max Problemi, basit bir optimizasyon problemidir. Problemin amacı, uygulanabilir bir çözümde olanların sayısını en üst düzeye çıkarmaktır. Problemin formülü aşağıda verilmiştir. Bu formülde yer alan D, problemin boyutunu belirtmektedir 🔖

Yukarıda formülünü görmekte olduğunuz maksimizasyon problemi için PSO algoritmasında kullanılacak maliyet fonksiyonu Sigmoid olarak belirlenmiştir.

Sigmoid fonksiyonu ise içerisine aldığı değerleri 0.5 ile kontrol etmektedir. Bu fonksiyon ile parçacıkların sahip olduğu Dimension içerisindeki tüm parçacıkların Sigmoid’ den gelen çıktısını 0.5 değerinin üzerine çıkarmaktır.

Böylelikle 0.5 değerinin üzerindeki çıktılar 1’e eşitlenecektir. Literatürdeki bu algoritma üzerinde çalışılmış diğer araştırmalar incelendiğinde parçacıkların hız değişim formülünde bulunan w, c1 ve c2 değerleri farklı alınmaktadır 💡

Sigmoid Fonksiyonu Çalışma Grafiği [5]

Wilcoxon ile İstatistiksel Sonuçlar

Öncelikle w değeri 0.005, c1 değeri 0.005 ve c2 değeri ise 0.009 seçilmiştir. Toplamda 40 adet parçacığın bulunduğu popülasyonda çalışılmaktadır. Bu değerler baz alındığında sırasıyla D=100, 500 ve 1000 boyutları için 30 kez çalıştırılmıştır. D olarak belirtilen değer problem boyutunu belirtmektedir. Buna göre aşağıdaki tabloda Wilcoxon ile hesaplanan sonuç değerleri yazdırılmıştır 📝

D problemin boyutu: 100 , iterasyon sayısı : 100.000 ve toplam 30 kez çalıştırma

Ortalama Medyan En iyi değer En kötü değer Standart Sapma
0.0031551897084034007 0.0025380204697822194 0.00023797210224091314 0.008994153476226206 0.0020874904616420636

D problemin boyutu: 500 , iterasyon sayısı : 100.000 ve toplam 30 kez çalıştırma

Ortalama Medyan En iyi değer En kötü değer Standart Sapma
0.0024457287103268333 0.002274384447498488 0.0001588232061854383 0.0001588232061854383 0.0016983186907986983

D problemin boyutu: 1000 , iterasyon sayısı : 100.000 ve toplam 30 kez çalıştırma

Ortalama Medyan En iyi değer En kötü değer Standart Sapma
0.0014781328189136006 0.0010733144689043976 7.397751636520865e-05 0.004376988570160589 0.0010840516145429367

Ardından w değeri 0.4, c1 değeri 1.5 ve c2 değeri ise 2 seçilmiştir. Toplamda 40 adet parçacığın bulunduğu popülasyonda çalışılmaktadır. Bu değerler baz alındığında sırasıyla D=100, 500 ve 1000 boyutları için 30 kez çalıştırılmıştır. D olarak belirtilen değer problem boyutunu belirtmektedir. Buna göre aşağıdaki tabloda Wilcoxon ile hesaplanan sonuç değerleri yazdırılmıştır 📝

D problemin boyutu: 100 , iterasyon sayısı : 100.000 ve toplam 30 kez çalıştırma

Ortalama Medyan En iyi değer En kötü değer Standart Sapma
0.10290449068126414 0.06354761821949564 0.001496700649763677 0.4405023200617695 0.11308392205322863

D problemin boyutu: 500 , iterasyon sayısı : 100.000 ve toplam 30 kez çalıştırma

Ortalama Medyan En iyi değer En kötü değer Standart Sapma
0.11090339649603935 0.07350043038100676 0.0010117064651082308 0.5125380033802425 0.11343766955639699

D problemin boyutu: 1000 , iterasyon sayısı : 100.000 ve toplam 30 kez çalıştırma

Ortalama Medyan En iyi değer En kötü değer Standart Sapma
0.1276016324307818 0.048701691139323475 0.0005810872467598704 0.7015965709030323 0.15191292927119768

🕵Bu değerler karşılaştırıldığında w, c1, c2 değerleri büyütüldükçe ortalama, medyan ve standart sapmanın büyüdüğü fark edilmektedir. Standart sapmanın büyük olması aynı zamanda serideki yani popülasyondaki parçacıkların ortalamadan saptığı anlamına gelir. Yukarıda tercih edilen değerler ile en iyi sonuç yani minimum değere daha kolay ulaşılmıştır.

🏋 İlk alınan değerlerdeki w değeri 0.005, c1 değeri 0.005 ve c2 değeri ise 0.009 olduğunda istenilen sonuca daha kolay ulaştığı gözlemlenmiştir. D=100,500 ve 1000. boyuta kadar artırıldığında en iyi konumun değerinin gittikçe küçüldüğü görülmüştür ve bu istenen bir durumdur.

NOT 🌠

PSO algoritması için geçerli olan best_globalbest değeri bir numpy dizisinde tutulmuş ve daha sonra Wilcoxon istatistiği uygulanarak aşağıdaki değerlere ulaşılmıştır.

📌Kodu incelemek isterseniz Github Reposu olarak sizlere yayınlıyorum. İyi çalışmalar dilerim 🐞

Diğer yazılarıma buradan ulaşabilirsiniz.

REFERANSLAR

[1] M. Yasin ÖZSAĞLAM, Mehmet ÇUNKAŞ, Optimizasyon Problemlerinin Çözümü için Parçacık Sürü Optimizasyonu Algoritması, Politeknik, Cilt:11 Sayı: 4 s.299-305, 2008.

[2] Fırat Üniversitesi, BMÜ-579 Metasezgisel Yöntemler, Parçacık Sürü Optimizasyonu.

[3] Pablo J. Villacorta, Swarm Intelligence Metaheuristics, part 2: Particle Swarm Optimization, https://www.stratio.com/blog/swarm-intelligence-metaheuristics-part-2-particle-swarm-optimization/.

[4] Muhammed Pektaş, Nisan 2019, Parçacık Sürü Optimizasyonu (PSO) Medium yazısından alınmıştır.

[5] https://en.wikipedia.org/wiki/Sigmoid_function adresinden alınmıştır.

Robots in Interior Design

Another dimension of the relationship between artificial intelligence and interior design can be seen as artificial intelligence-based products used in the production process. One of these products is 3D printers. Although these printers are not a new product today, they remain up-to-date due to the development over time.

İÇ MEKAN ÜRETİMİNDE ROBOTLAR

Yapay zeka ve iç mekan tasarım arasındaki ilişkinin bir başka boyutu üretim sürecinde kullanılan yapay zeka tabanlı ürünler olarak görülebilir. Bu ürünlerden biri de 3D yazıcılardır. Bu yazıcılar günümüzde yeni bir ürün olmasa da zaman içerisinde gösterdiği gelişim nedeniyle güncelliğini korumaktadır.

Simulated Annealing Algorithm

Hello everyone, the word optimized is a word that we encounter very often in everyday life. As you know, the word optimization is the case where an event, problem, or situation chooses the best possible possibilities within a situation 📈. The Simulated Annealing method, which helps to find the best result by obtaining the results of the problem at different times in order to find a general minimum point by moving towards the value that is good from these results and testing multiple solutions, is also an optimization problem solution method [1].

🔎About the Simulated Annealing Algorithm

The simulated annealing method is a popular metaheuristic local search method used to address discrete and to a lesser extent continuous optimization problem. The main feature of simulated annealing is that it provides a means of evading the local optimality by allowing hill climbing movements (movements that worsen the purpose function value) with the hope of finding a global optimum [2].

The reason why the algorithm is called annealing is since the blacksmith’s heat treatment to a certain degree while beating the iron is based on the iron’s desired consistency. The problem is addressed with the same logic as in this example, and the heating process is passed with the degree of annealing, and then it is assumed that it reaches the desired point. (Local Objective Function)  

The function that gives the probability of acceptance of motion leading to an elevation up to Δ in the objective function is called the acceptance function [4].

Probability formula

When the temperature is high, there will be a very high probability of acceptance of movements that may cause an increase in goal function, and this probability will decrease as the temperature decreases. For this reason, it is necessary to start the search with a sufficiently high temperature value [4]. I have determined the initial temperature value to be used in the project I’ m working on as T= 100000 🌡️. In the algorithm, the search process is continued by trying a certain number of movements at each temperature value while the temperature is gradually reduced [4].

Flow Chart of The Algorithm 🖋

Working Principle of Algorithm 📲

The most important operation in the running logic of the simulated algorithm is that the temperature must be cooled over time. Because if the initial temperature does not decrease over time, the energy will remain consistently high and the search of  the energy levels are compared in each solution until the cooling process is performed in the algorithm. In the calculation of Energy Exchange, the current configuration difference is utilized from a possible configuration as pos’ [5].

Calculation of Energy Exchange [5]

A calculation probability is then presented for calculating the position to be accepted, as seen in Figure 4. The equation is simplified by ignoring the Boltzmann constant k. In this way, it is possible to calculate the new candidate solution.

Probability calculation of new candidate solution [5]

            In these cases, the temperature of T continues to decrease at a certain interval repeating. The data set used in this project is ‘gr137.tsp’. This data set works with the TSP infrastructure and is based on mobile vendor problems. This data set contains information for 666 city problems in the American infrastructure and provides 137 x and Y coordinates in the content size. We will compare the nodes executed in the simulated annealing method by first replacing them with the swap method and try to get the best result 👩🏻‍🏫.

Preview from file ‘gr137.tsp’  with coordinates

  We will calculate the distances of the nodes to be compared in the objective function as follows. Here we take the distance to be calculated as the Euclidean distance 📏.

We will continue to encode in Python, which is a very common language in optimization algorithms. Let’s write together the objective function based on Euclidean distance 👍.

Purpose function distance calculation

Calculation with Swap Method 🧮

As shown in Figure 8, the value denoted by N represents the size of the coordinates. We will assign swap1 and swap2 variables by generating random values in size N. If the two values to be checked are the same as each other, swap2 will re-create the probability to create a new probability value. In this data set, the value expressed by p is equivalent to the Id column. Values ​​are copied with the copy( ) function to prevent any changes. The reason for calculating energy at each stage is because the temperature value in the Simulated Annealing algorithm logic must be heated to a certain value and then cooled to a certain level by a cooling factor called cooling factor. In the case of simulated annealing, there will be an increase in energy due to the mobility of the particles in the heating process and it is desired to check whether they have high energy by making energy calculations in each process ⚡.

Calculation with Swap method

Since this method is used in the algorithm, it can not go to the method of calculating random values so it is very important in terms of time to go to the correct results with the use of other search operators.

Swap exchange method between values

DatasetOptimumBestWorstMeanStandard Deviation
gr137.tsp69853854.7855305691671868.838856972194863.772459811443.9530597090364

The first solution and best solution values in iteration outputs are shown below respectively. We will achieve the first solution and last solution values throughout 10 iterations by aiming to reach the optimum values.

Table of Objective values
Graphization of Objective values

E.g. 5.the results obtained at different times during the calculation to observe the value changes during iteration are shown below. Thus, the logic of the swap process and the energy changes (ΔE) in this process can be seen.

Showing energy values while swaps are in progress

Result values based on calculation in Link 5 and 102

Result values, depending on the calculation in links 113 and 127

🔎 APPLYING THE ALGORITHM 2-OPT OVER S.A.

2-opt algorithm is probably the most basic and widely used algorithm for solving TSP problems [6]. Basically, it can be defined as the deletion of the two edges in the round and the Connecting of the round divided into two parts in a different way to reduce costs. (Gutin ve Punnen, 2002).

✔️ In the swap method of simulated annealing, the two values are controlled by each other and stored according to the probability value. However, since all operations will be done in sequence, it will not be very efficient in terms of runtime.

✔️With the 2-opt algorithm, it is seen that the index values (initial_p) have passed to the 17th node after the 4th node. The 2 opt algorithm enters the circuit by breaking the link between nodes 4 and 5 and creating the link between nodes d and 17. Thus, runtime produces more efficient results.

Connecting different values in tour connection

In the two_opt_python function, the index values in the cities are controlled with 2 increments and change. If there is a change in the path on the Tour, this change is assigned to the tour variable. as a result of the dist( ) function, the Euclidean distance between two cities ( such as 4-17) is calculated and the coordinates in the tour are returned. This ensures improvement on the best solution ⭐

REFERENCES

[1] Sadi Evren Seker, Computer Concepts, “Simulated Annealing”, Retrieved from http://bilgisayarkavramlari.sadievrenseker.com/2009/11/23/simulated-annealing-benzetilmis-tavlama/.

 [2] Darrall Henderson, Sheldon H Jacobson, Alan W. Johnson, The Theory and Practice of Simulated Annealing, April 2006.          

 [3] Orhan Baylan, “WHAT IS HEAT TREATMENT? WHY HEAT TREATMENT IS DONE TO STEEL?”, Retrieved from https://www.metaluzmani.com/isil-islem-nedir-celige-nicin-isil-islem-yapilir/.

 [4] Annealing Simulation Algorithm (Simulated Annealing), BMU-579 Simulation and modeling , Assistant Prof. Dr. Ilhan AYDIN.

[5] Hefei University, Thomas Weise, Metaheuristic Optimization, 7. Simulated Annealing.

[6] Timur KESKINTURK, Baris KIREMITCI, Serap KIREMITCI, 2-opt Algorithm and Effect Of Initial Solution On Algorithm Results, 2016.

Benzetimli Tavlama (Simulated Annealing) Algoritması

BENZETİMLİ TAVLAMA ALGORİTMASI

Herkese merhabalar, optimize kelimesi aslında günlük hayatta çok sık karşımıza çıkan bir kelimedir. Takdir edersiniz ki optimizasyon kelimesi aslında bir olayın, problemin veya bir durumun içerisindeki olasılıklardan mümkün olan en iyiyi seçmesi durumudur 📈.

Genel bir minimum noktası bulmak amacı ile problemin farklı zamanlarındaki sonuçlarını elde ederek bu sonuçlardan iyi olan değere doğru hareket edip birden fazla çözümü test ederek en iyi sonucu bulmaya yardımcı olan yöntem olan Simulated Annealing (Benzetimli Tavlama) yöntemi de bir optimizasyon problemi çözüm yöntemidir [1].

[gdlr_core_space height=”30px”]

🔎Simulated Annealing Algoritması Hakkında

Benzetimli tavlama (Simulated Annealing) yöntemi, ayrık ve daha az ölçüdeki sürekli optimizasyon problemlerini ele almak için kullanılan popüler bir metasezgisel yerel arama yöntemidir.

Benzetimli tavlama algoritmasının temel özelliği, küresel bir optimum bulma umudu ile tepe tırmanma hareketlerine (amaç fonksiyon değerini kötüleştiren hareketlere) izin vererek yerel optimumdan kaçma aracı sağlamasıdır [2].

Algoritmaya tavlama ismi verilmesinin sebebi, demircilerin demiri döverken belirli bir dereceye kadar ısıl işlemden geçirmesi sonucu demirin istenilen kıvama gelmesini esas almasından kaynaklanmaktadır. Aynı mantık ile bir problem ele alınarak tavlama derecesi ile ısıtma sürecinden geçiriliyor ve ardından istenilen noktaya geldiğinde sonuca ulaştığı kabul ediliyor. (Local Objective Function)  

Demirin ısıl işlemden geçirilerek tavlanması [3]

[gdlr_core_space height=”30px”]

Amaç fonksiyonunda Δ kadar bir yükselmeye yol açan hareketin kabul edilme olasılığını veren fonksiyon kabul (accept) fonksiyonu olarak adlandırılır [4].

Olasılık formülü

[gdlr_core_space height=”30px”]

Sıcaklık yüksek olduğunda, amaç fonksiyonunda artışa neden olabilecek hareketlerin kabul edilme olasılığı çok yüksek olacak, sıcaklık düştükçe bu olasılık da azalacaktır. Bu sebeple, aramaya yeteri kadar yüksek bir sıcaklık değeri ile başlamak gereklidir [4]. Ben çalıştığım projede kullanılacak başlangıç sıcaklık değerini T= 100000 olarak belirledim 🌡️.

Algoritmada, sıcaklık yavaş yavaş azaltılırken her sıcaklık değerinde belli sayıda hareket deneyerek arama işlemi sürdürülmektedir [4].

[gdlr_core_space height=”30px”]

Algoritmanın Akış Şeması 🖋️

Benzetimli Tavlama Algoritması Akış Diyagramı

[gdlr_core_space height=”30px”]

Algoritmanın Çalışma Prensibi 🔨

Benzetimli algoritmanın çalışma mantığında en önemli işlem, sıcaklığın zamanla soğutulması gerektiğidir. Çünkü başlangıç sıcaklığı zamanla azalmazsa enerji sürekli yüksek kalacak ve yüksek orandaki entropi ile tüm ağacın aranması sağlanacaktır, bu istenmeyen bir durumdur.

Algoritmada soğuma işlemi gerçekleştirilene kadar her çözümde enerji seviyeleri karşılaştırılır. Enerji değişimi hesaplanmasında pos’ olarak olası bir yapılandırmadan mevcut yapılandırma farkından faydalanılır [5].

Enerji değişimi hesaplanması [5]

Daha sonra kabul edilecek pozisyonun hesaplanması için Şekil 4’ de görüldüğü gibi bir hesaplama olasılığı sunulmuştur. Boltzmann sabiti olan k değeri göz ardı edilerek denklem sadeleştirilmiştir. Bu sayede yeni aday çözümün hesaplanmasına imkân sunulmuştur.

Yeni aday çözümün olasılık hesabı [5]

[gdlr_core_space height=”30px”]

Bu durumlarda T sıcaklığı ise yinelenen belirli bir aralıkta sıcaklığını azaltmaya devam etmektedir. Bu projede kullanılan veri seti ‘gr137.tsp’ olarak seçilmiştir.

Bu veri seti TSP alt yapısı ile çalışmakta ve gezgin satıcı problemlerini baz almaktadır. Bu veri seti Amerika alt yapısındaki 666 tane şehir problemi için bilgi içermekte ve içerik boyutunda 137 tane X ve Y koordinatları verilmektedir.

Benzetimli tavlama yönteminde çalıştırılan düğümleri öncelikle swap yöntemi ile değiştirerek karşılaştıracağız ve en iyi sonucu elde etmeye çalışacağız 👩🏻‍🏫

Koordinatların yer aldığı “gr137.tsp” dosyasından ön izleme

[gdlr_core_space height=”30px”]

Amaç fonksiyonu olarak gösterilen Objective Function ’da karşılaştırılacak düğümlerin mesafelerini aşağıdaki gibi hesaplayacağız. Burada hesaplanacak mesafeyi ise öklid mesafesi olarak alacağız 📏

Optimizasyon algoritmalarında çok sık kullanılan bir dil olan Python dilinde kodlamaya devam edeceğiz. Haydi birlikte amaç fonksiyonunu öklid mesafesi baz alarak yazalım 👍

[gdlr_core_space height=”30px”]

Amaç fonksiyonu mesafe hesaplanması

Swap Yöntemi ile Hesaplama 🧮

Şekil 8’ de görüldüğü üzere N ile gösterilen değer koordinatların boyutunu ifade etmektedir. N boyutunda rastgele değerler üreterek swap1 ve swap2 değişkenlerine atayacağız. 

Kontrol edilecek iki değer birbiri ile aynı ise yeni olasılık değeri oluşturmak üzere swap2 olasılığı yeniden değer oluşturacak demektir. Bu veri setinde p ile ifade edilen değer bir bakıma Id sütununa denk gelmektedir. 

Üzerinde değişiklik yapılmaması için copy( ) fonksiyonu ile değerler kopyalanmaktadır. Her aşamada enerji hesaplaması yapılmasının sebebi, Simulated Annealing algoritma mantığındaki sıcaklık ( temperature ) değerinin belirli bir değere kadar ısıtılması ve sonra cooling factor denilen soğuma faktörü ile belirli bir seviyeye kadar soğutulması gerektiğinden kaynaklanmaktadır.

Benzetimli tavlama örneğindeki ısınma sürecinde içerisindeki partiküllerin hareketliliğinden dolayı enerji yükselmesi olacaktır ve enerji hesabı her süreçte yapılarak yüksek enerjiye sahip olup olmadığı kontrol edilmek istenmektedir ⚡

[gdlr_core_space height=”30px”]

Swap yöntemi ile hesaplama

Algoritmada kullanılan bu yöntemde sıra ile (order) işlem yapılmakta olduğundan rastgele değerler üzerinde hesaplama yöntemine gidemez böylelikle doğru sonuçlara diğer arama operatörlerinin kullanımı ile gidilmesi zaman açısından da çok önem arz etmektedir.

Değerler arasında swap değişim yöntemi

Veri Seti Optimal En iyi En kötü Ortalama Standart Sapma
gr137.tsp 69853 854.7855305691671 868.838856972194 863.77245981144 3.9530597090364

İterasyon çıktılarındaki ilk çözüm ve elde edilen en iyi çözüm değerleri ise sırasıyla aşağıda gösterilmektedir. Optimum değerleri ulaşmayı hedefleyerek 10 iterasyon boyunca ilk çözüm ve son çözüm değerlerini elde edeceğiz.

Objective değerler tablosu

Objective değerlerin grafikselleştirilmesi

[gdlr_core_space height=”30px”]

Örneğin 5.iterasyon çalıştırılırken değer değişimlerini gözlemlemek amacı ile hesaplama sırasında farklı zamanlarda alınan sonuçlar aşağıda gösterilmiştir. Böylelikle swap işlemi mantığını ve bu süreçteki enerji değişimleri (ΔE) gözle görülebilmektedir.

Swap işlemi devam ederken enerji değerlerinin gösterilmesi

5 ve 102 nolu bağdaki hesaplamaya bağlı result değerleri

113 ve 127 bağındaki hesaplamaya bağlı olarak result değerleri

[gdlr_core_space height=”30px”]

🔎 2-OPT ALGORİTMASININ SA ÜZERİNDE UYGULANMASI

2-opt algoritması, GSP problemlerinin çözümüne yönelik, muhtemelen en temel ve çok geniş kullanım alanına sahip bir algoritmadır [6]. Temel olarak tur içerisindeki iki kenarın silinmesi ve iki parçaya ayrılan turun maliyetleri düşürecek şekilde, farklı olarak bağlanması şeklinde tanımlanabilir (Gutin ve Punnen, 2002).

✔️Benzetimli tavlamanın swap yönteminde iki değer birbiri ile kontrol edilmekte ve olasılık değerine göre hafızaya alınmaktadır. Fakat tüm işlemler sırası ile yapılacağından çalışma zamanı açısından çok verimli olmayacaktır.

✔️2opt algoritması ile örneğin tour olarak adlandırılan indis değerlerinde (initial_p) 4. düğümden sonra 17. düğüme geçiş yapmakta olduğu görülmektedir. 2opt algoritması devreye 4 ve 5. düğümler arasındaki bağı kırıp d ile 17 düğümleri arasındaki bağı oluşturmakta girer. Böylelikle çalışma zamanı daha verimli sonuçlar üretir.      

[gdlr_core_space height=”30px”]

Tour bağlantısındaki farklı değerlerin bağlanması

two_opt_python fonksiyonunda şehirlerdeki indis değerleri 2 artırımlı olarak kontrol edilerek değişimi vermektedir. Tour üzerindeki yolda herhangi bir değişim yaşandıysa bu değişim tour değişkenine atanmaktadır. dist( ) fonksiyonu sonucunda iki şehir arasındaki ( 4-17 gibi) Öklid uzaklığı hesaplatılarak tour içerisindeki koordinatlar döndürülmektedir. Bu sayede en iyi çözüm üzerinde iyileştirme sağlanmaktadır ⭐

REFERANSLAR

[1] Sadi Evren Şeker, Bilgisayar Kavramları, “Simulated Annealing (Benzetilmiş Tavlama)”, http://bilgisayarkavramlari.sadievrenseker.com/2009/11/23/simulated-annealing-benzetilmis-tavlama/ adresinden alınmıştır.

 [2] Darrall Henderson, Sheldon H Jacobson, Alan W. Johnson, The Theory and Practice of Simulated Annealing, April 2006.          

 [3] Orhan Baylan, “ISIL İŞLEM NEDİR? ÇELİĞE NİÇİN ISIL İŞLEM YAPILIR?”, https://www.metaluzmani.com/isil-islem-nedir-celige-nicin-isil-islem-yapilir/ adresinden alınmıştır.     

 [4] Tavlama Benzetimi Algoritması (Simulated Annealing), BMÜ-579 Benzetim ve Modelleme, Yrd. Doç. Dr. İlhan AYDIN.

[5] Hefei University, Thomas Weise, Metaheuristic Optimization, 7. Simulated Annealing.

[6] Timur KESKİNTÜRK, Barış KİREMİTCİ, Serap KİREMİTCİ, 2-OPT Algoritması ve Başlangıç Çözümünün Algoritma Sonuçları Üzerindeki Etkisi, 2016.