الصفحة الرئيسية>المتعلقة بالبرمجة>شفرة المصدر الأخرى
تنزيل

مشكلة بائع السفر باستخدام تحسين ANT Colony

مقدمة

تحسين مستعمرة النمل

يعد تحسين Colony Optimization (ACO) تقنية تلويبية في مجال ذكاء السرب. إنه يستخدم لحل مشاكل التحسين التوافقي المختلفة.

يعتمد ACO على سلوكيات ANT Colony وقدرة البحث الخاصة بها لتحسين التوافقي. يظهر تحليل السلوك الطبيعي لمستعمرات النمل أن النمل يتحرك على طول توزيع الفيرومون الغني على طريقهم. الخوارزمية تقليد هذا السلوك.

مشكلة البائع في السفر

مشكلة البائع المتجهة (TSP) هي مشكلة خوارزمية كلاسيكية تركز على التحسين.

غالبًا ما يعني الحل الأفضل حلًا أرخص أو أقصر أو أسرع.

تصف المشكلة بائعًا يجب أن يسافر بين مدن N ، بحيث يزور كل مدينة مرة واحدة خلال رحلته. كل مدينة متصلة بالمدن الأخرى ، والروابط لها أوزان ثابتة (تكاليف السفر ، والمسافة ، إلخ)

مجموعة البيانات

تتكون مجموعة البيانات من 225 مدينة في الجزء الشمالي الغربي والوسط من القارة الهندية الفرعية.

بنية مجموعة البيانات 
 tsp dataset/
    ├── distance.txt
    ├── location_ll.txt
    ├── location_map.jpg
    ├── location_map_satellite_image.jpg
    ├── names.txt
    ├── road_distance.txt
    └── travel_time.txt
وصف الملف
ملف وصف
location_ll.txt مواقع جغرافية مفصولة الفضاء (خط العرض وخط الطول) لكل مدينة.
المسافة المسافة القوية بين المدن.
Road_distance.txt المسافة عن طريق الطريق بين المدن.
travel_time.txt الوقت يستغرق السفر من مدينة إلى أخرى.

الخوارزميات

نظام مستعمرة النمل

في نظام مستعمرة النمل (ACS) ، يتم وضع عدد من النمل الاصطناعي في البداية في مدن عشوائية. كل نملة تبني جولة (حل ممكن من TSP). يختار المدينة التالية من خلال تطبيق قاعدة انتقال الدولة (قاعدة الجشع). توفر هذه القاعدة توازنًا بين استكشاف الحواف الجديدة واستغلال المعرفة المتراكمة.

يتم إيداع كمية ثابتة من الفيرومون بواسطة كل نملة في كل خطوة على الطريق الأكثر ملاءمة (أفضل جولة)

النخبوي

باستخدام نهج النخبوي ، نحاول التحكم في معلمات التعلم. يتم مكافأة النمل الذي يجد أفضل طريق (الجودة) أكثر من النمل الآخر. يتم إيداع المزيد من الفيرومون على طرق أفضل ، مما يعطي أهمية لتلك الجولة بالذات ويقلل من الوقت للحصول على حل الأمثل.

كمية الفيرومون المودعة على أساس جودة المسار.

ماكسمين

تهدف طريقة Maxmin إلى الحصول على أفضل ما في العالمين ، وهو قريب من الحل الأمثل مع وقت تنفيذ سريع. ويتحقق ذلك من خلال تغيير المبلغ للفيرومون المودعة من خلال الخطوات.

في البداية يكون الوزن مرتفعًا ، مما يعطي معدل تعليمي سريع. الوزن يتناقص تدريجيا حتى 75 ٪ الانتهاء. ثم إذا تم ضبط النموذج إذا تم ضبطه جيدًا عن طريق تطبيق الأوزان من خلال مقارنة النتائج بجولة أفضل عالمية .

في نهاية كل خطوة ، تكون الأوزان مرتبطة داخل حدود الحد الأقصى للفيرومون لمنع الحل للضل.

تنخفض كمية الفيرومون تدريجياً لأول 75 ٪ من التكرارات. ثم يعتمد المبلغ على الجودة مقارنة بأفضل جولة.

حدود 
 params = {
    '_colony_size' : "number of ants in the colony"  ( default = 15 ),
    '_steps' : "iteration to run through" ( default = 50 ),
    '_mode' : "mode of algorithm to run the model"
}
الاستخدام 
 # Import model
from aco_tsp import SolveTSPUsingACO

# Setup parameters
_colony_size = 15
_steps = 50

# Select mode
# ['ACS', 'Elitist', 'MaxMin']
_mode = 'ACS'

# Nodes (latitude and longitude)
_nodes = [( 20.05961 , 77.949783 ), ( 17.075451 , 74.628664 ), ..., ( 19.4133545 , 80.0059101 )]
s
# Model setup and run
model = SolveTSPUsingACO (
    mode = _mode ,
    colony_size = _colony_size ,
    steps = _steps ,
    nodes = _nodes
)

runtime , distance = model . run ()

نتيجة

بمساعدة ACO ، ننشئ طريقًا مثاليًا لتغطية جميع المدن أثناء محاولة تقليل مسافة السفر إلى الحد الأدنى. تعتمد النتيجة أيضًا على معلمات الخوارزمية والأوزان الحافة (travel time, distance, road_distance) المستخدمة لتحسين المسار.


الشكل: تتبع المسار الأمثل من خلال المدن

يوسع
معلومات إضافية
تطبيقات ذات صلة
نوصي لك
أخبار ذات صلة الكل