خوارزمية جدولة خاصة (توسيع النمط)

Question

سؤال
هل تعتقد أن الخوارزميات الوراثية تستحق المحاولة للمشكلة أدناه، أو هل سأضغط على مشاكل الدنيم المحلية؟

أعتقد أن جوانب المشكلة رائعة بالنسبة لإعداد نمط مولد / للياقة البدنية. (إذا كنت قد فاشلت مشروعا مشابها، فأنا أحب أن أسمع منك، ولا أفعل شيئا مشابها)

شكرا لك على أي نصائح حول كيفية هيكل الأشياء وأظافر هذا الحق.

المشكلة
أنا أبحث في خوارزمية جدولة جيدة لاستخدامها لمشكلة العالم الحقيقي التالية.

لدي تسلسل مع 15 فتحة مثل هذا (قد تختلف الأرقام من 0 إلى 20):

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

(وهناك في المجموع 10 تسلسل مختلف من هذا النوع)

يحتاج كل تسلسل إلى التوسع في صفيف، حيث يمكن أن تأخذ كل فتحة موضع واحد.

1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 

القيود المفروضة على المصفوفة هي:

• صف حكيم، أي أفقيا] يجب أن يكون عدد منها، إما 11 أو 111
• صف حكيم] المسافة بين تسلسلتين من 1 يحتاج إلى الحد الأدنى من 00
• يجب أن يتطابق مجموع كل عمود مع الصفيف الأصلي.
• يجب تحسين عدد الصفوف الموجودة في المصفوفة.

يحتاج الصفيف ثم إلى تخصيص واحد من 4 مصفوفة مختلفة، والتي قد يكون لها عدد مختلف من الصفوف:

A, B, C, D

A، B، C و D هي أقسام في العالم الحقيقي. يجب وضع الحمل معرضا بشكل معقول خلال فترة 10 أيام، وليس للتدخل في أهداف الإدارة الأخرى.

تتم مقارنة كل من المصفوفة بتوسيع 10 تسلسلات أصلية مختلفة لذلك لديك:

A1, A2, A3, A4, A5, A6, A7, A8, A9, A10
B1, B2, B3, B4, B5, B6, B7, B8, B9, B10
C1, C2, C3, C4, C5, C6, C7, C8, C9, C10
D1, D2, D3, D4, D5, D6, D7, D8, D9, D10

قد يتم حجز بعض المواقع الموجودة على هذه (لست متأكدا مما إذا كان ينبغي علي أن أجعلها محفوظة فقط / غير محجوزة أو قائمة على الوظيفة). قد تكون البقع المحجوزات اجتماعات وغيرها من الأحداث

يجب أن يكون مجموع كل صف (على سبيل المثال كل شيء) تقريبا نفس الشيء في غضون 2٪. يجب أن يكون أي مبلغ (A1 من خلال A10) تقريبا مثل (B1 من خلال B10) إلخ.

يمكن أن يختلف عدد الصفوف، لذلك لديك على سبيل المثال:

A1: 5 صفوف A2: 5 صفوف A3: 1 صف، حيث يمكن أن يكون هذا الصف الفردي على سبيل المثال:

0 0 1 1 1 0 0 0 0 0 0 0 0 0 0

إلخ..

مشكلة الفرعية *

سأكون سعيدا جدا لحل جزء فقط من المشكلة. على سبيل المثال القدرة على المدخل:

1 1 2 3 4 2 2 3 4 2 2 3 3 2 3

واحصل على مجموعة مناسبة من التسلسلات مع 1 و 0 التقليل من عدد الصفوف بعد القيود المتابعة أعلاه.

Answer 1

محاولة حل المشكلة الفرعية

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

أساس ناقلات

بادئ ذي بدء، يجب أن تولد ما أفكر به كمنتجات الأساس. على سبيل المثال، إذا كان التسلسل الخاص بك كان 3 أرقام طويلة بدلا من 15، فستكون ناقلات الأساس:

v1 = [1 1 0]

v2 = [0 1 1]

v3 = [1 1 1]

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

a*v1 + b*v2 + c*v3

حيث A، B و C هي أعداد صحيحة إيجابية. للتسلسل [1 2 1]، الحل هو v1 = 1، v2 = 1، v3 = 0. ما تريد أولا القيام به هو العثور على جميع ناقلات الأساس المحتملة الطول 15. من حساباتي الفعلية أعتقد أنه هناك في مكان ما بين 300-400 ناقلات الطول 15. يمكنني أن أعطيك بعض النصائح نحو توليدها إذا كنت تريد.

إيجاد الحلول

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

لذلك نحن نأخذ ناقلات الأساس الأول (واحد مع أكبر مبلغ / حجم) وطرح هذا المتجه من التسلسل حتى ننشئ نتيجة غير قابلة للحمل (وجود 0 1 0 في ذلك على سبيل المثال) أو أي من الأرقام في النتيجة هو سلبي. نقوم بتخزين عدد المرات التي نطرحنا ناقلها في Veccooke. نستخدم النتيجة بعد طرح ناقلات الأساس من التسلسل باعتباره التسلسل لنطق الأساس التالي. إذا لم يتبق السفلو الأصفار في النتيجة، فإننا نتوقف عن الحلقة.

لست متأكدا من كفاءة / دقة هذه الطريقة، لكنها قد تعطيك على الأقل بعض الأفكار.

حلول أخرى ممكنة

فكرة أخرى لحل هذا هي استخدام ناقلات الأساس وتشكيل المشكلة كمشكلة تحسين / أقل مربعات. تشكل مصفوفة من ناقلات الأساس بحيث ستقلل المشكلة الأساسية مجموع [(AX - B) ^ 2] حيث تكون مصفوفة ناقلات الأساس، B هي تسلسل الإدخال، و X هي معاملات ناقلات الأساس. ومع ذلك، فأنت تريد أيضا تقليل عدد الصفوف، حتى تتمكن من إضافة مصطلح مثل x ^ t * x إلى وظيفة التقليل حيث x ^ t هو تبديل x. إن الجزء الصعب في رأيي هو إيجاد مصطلحات مختلفة لإضافة التي ستشجع معاملات ناقلات عدد صحيح. إذا كنت تستطيع التفكير في طريقة للقيام بذلك، فيمكن أن يكون التحسين جيدا وسيلة جيدة للقيام بذلك.

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

Answer 2

يمكن تطبيق GA على هذه المشكلة، لكن لن تكون مهمة 5 دقائق. تحتاج إلى وضع عدة أشياء معا، دون معرفة تنفيذ كل منهم هو الأفضل.
لذا:

1. تمثيل الحل - كيف ستمثل الحل المحتمل؟ يبدو أن استخدام مصفوفة أكثر مباشرة إلى الأمام. باستخدام مجموعة من صفيفات الأبعاد واحدة ممكن أيضا. ولكن لديك بعض الأوامر، لذلك ربما مفهوم Supergene يستحق النظر؟
2. يجب عليك استخدام مشغلي الطفرة / كروس المناسبة لتمثيل الجينات المعطاة.
3. كيف ستحدد تقييد الحلول؟ تدمير تلك التي ليست مناسبة؟ ماذا لو كانت تحتوي على معلومات قيمة؟ ربما دعهم يبقون في عدد السكان ولكن إضافة بعض العقوبة إلى اللياقة البدنية، لذلك سوف يسهمون في ذرية، لكن لن يذهب إلى الأجيال القادمة؟

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

PS البصيرة الشخصية: كنت حل مشكلة ملكات N، لمدة 70 <n <100 (لوحة NXN، N Queens). كانت الخوارزمية تعمل بشكل جيد لانخفاض n (ربما كان يحاول كل الجمع؟)، ولكن مع N في هذا النطاق، لم أستطع العثور على الحل المناسب. قفزت اللياقة البدنية بسرعة إلى حوالي 90٪ من الحد الأقصى، ولكن في النهاية كان هناك دائما ملكات اثنين متضاربة. لكنه كان تنفيذ ساذج للغاية.