New lower bounds for constant-weight codes via seeded bit-swap tabu search

تخيل أنك تحاول حزم حقيبة سفر، ولكن بقاعدة غريبة للغاية: كل قطعة تضعها في الحقيبة يجب أن تكون بنفس الحجم تمامًا، ولا يمكن لقطعتين أن تكونا متشابهتين جدًا. إذا كانتا متشابهتين للغاية، فقد تختلطان في الظلام، مما يسبب الفوضى. في عالم الاتصالات الرقمية، هذه "الحقيبة" هي رسالة، و"القطع" هي أنماط من الأصفار والآحاد (البتات)، و"الحجم" هو عدد الآحاد في النمط. هذا هو لغز الأكواد ذات الوزن الثابت (constant-weight codes). يستخدم العلماء هذه الأكواد لإرسال البيانات بشكل موثوق عبر القنوات المليئة بالضجيج، مثل شبكات Wi-Fi أو راديو الفضاء العميق، مما يضمن أنه حتى لو تعرضت بعض البتات للتشويه، يمكن للمستقبل معرفة ما تم إرساله. الهدف بسيط ولكنه صعب للغاية: وضع أكبر عدد ممكن من القطع الفريدة والمتميزة داخل الحقيبة دون أن تتصادم مع بعضها البعض. كلما كبر حجم الحقيبة (أي عدد الأكواد التي يمكنك وضعها)، زادت كمية المعلومات التي يمكنك إرسالها في وقت واحد.

هنا يأتي ويليام إيكولز، الذي قرر معالجة مشكلة التعبئة هذه بلمسة ذكية. فبدلاً من البدء بحقيبة فارغة ورمي القطع فيها عشوائيًا، آملًا أن تتناسب، استخدم نهجًا "بذرة" (seeded approach). فكر في الأمر على هذا النحو: إذا كنت تريد بناء قلعة ليجو أفضل، فأنت لا تبدأ من الصفر فحسب؛ بل تأخذ قلعة موجودة بالفعل بجودة عالية، وتنزع منها بعض الطوب، وتبدلها لترى ما إذا كان بإمكانك جعلها أكبر أو أكثر متانة. استخدم إيكولز طريقة حاسوبية تسمى البحث التابو (tabu search)، وهي تشبه المستكشف العنيد الذي يرفض تكرار خطواته (لتجنب الوقوع في حلقات مفرغة) ويستمر في تجربة مسارات جديدة. ومن خلال "تزويد" هذا المستكشف بـ "بذور" من تصميمات أكواد موجودة وعالية الجودة، وجهه نحو العثور على 124 ترتيبًا جديدًا وأكبر للتعبئة لم يتم اكتشافها من قبل. هذه الترتيبات الجديدة تحسن الحدود الدنيا لكيف تفضل عدد الرسائل التي يمكننا إرسالها، كما أنها تساعدنا في فهم عدد الكرات التي يمكن أن تلمس كرة مركزية في فضاء عالي الأبعاد — وهو مفهوم يُعرف باسم "أرقام التقبيل" (kissing numbers).

لغز التعبئة والبذرة السحرية

في العالم الرقمي، البيانات هي مجرد سلسلة طويلة من الأصفار والآحاد. أحيانًا، لجعل الأمور قوية، نسمح فقط بالسلاسل التي تحتوي على عدد محدد من الآحاد. على سبيل المثال، إذا قلنا إن "الوزن" هو 5، فيجب أن تحتوي كل سلسلة على خمسة آحاد بالضبط والباقي أصفار. الآن، تخيل أن لديك مجموعة من هذه السلاسل. لمنع الأخطاء، يجب أن تكون كل سلسلة في مجموعتك مختلفة بما يكفي عن أي سلسلة أخرى. إذا كانت سلسلتان متشابهتين للغاية، فقد يؤدي القليل من الضجيج إلى تحويل إحداهما لتصبح الأخرى، وسيرتبك المستقبل. تُقاس "المسافة" بينهما بعدد المواضع المختلفة.

السؤال الكبير في هذا المجال هو: ما هو أقصى عدد من السلاسل التي يمكنك وضعها في مجموعتك؟ هذا العدد الأقصى يسمى $A(n, d, w)$، حيث $n$ هو طول السلسلة، و$d$ هو الحد الأدنى للمسافة المطلوبة، و$w$ هو عدد الآحاد. لعقود من الزمن، حاول الرياضيون وعلماء الكمبيوتر إيجاد أكبر المجموعات الممكنة لمختلف الإعدادات. لقد وجدوا مجموعات رائعة، لكنهم غالبًا لا يعرفون ما إذا كانوا قد وجدوا أكبر مجموعة ممكنة على الإطلاق. هم يعرفون فقط أنهم لا يستطيعون التفوق على رقم معين.

استراتيجية "التزويد بالبذور"

كانت المحاولات السابقة للعث find هذه الأعداد القصوى باستخدام عمليات البحث الحاسوبية تبدو وكأنها تجول في غابة مظلمة. كانت الحواسيب تبدأ بتخمينات عشوائية، وبينما كانت تجد أحيانًا مسارات جيدة، إلا أنها غالبًا ما كانت تتعثر في مساحات خالية محلية تبدو وكأنها قمة الجبل لكنها ليست كذلك. كانت تتوقف هناك، ظناً منها أنها وجدت أفضل كود ممكن، بينما كان هناك كود أكبر بكثير خلف التل التالي مباشرة.

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

فعل ذلك بطريقتين مرحتين:

1. التزويد المباشر: أخذ كودًا موجودًا وأضاف إليه كلمة واحدة إضافية، اختيرت بعناً لتقليل قدر الإمكان من "المشاكل" (عجز المسافة). خلق هذا نقطة انطلاق أكبر قليلاً وأكثر فوضوية.
2. تزويد الجوار: نظر في الأكواد لمشاكل مختلفة قليلاً. على سبيل المثال، إذا أراد كوداً بطول 30، فقد يأخذ كوداً ممتازاً بطول 29، ويضيف صفراً لكل كلمة لجعل طولها 30، ثم يستخدم ذلك كنقطة انطلاق. أو ربما يأخذ كوداً بطول 31، ويقص منه صفراً، ويستخدمه.

بمجرد حصوله على نقاط الانطلاق "المزودة بالبذور" هذه، قام بتشغيل بحث التابو لتبديل البتات (bit-swap tabu search). تخيل هذا البحث كلعبة كراسي موسيقية حيث الكراسي هي مواضع الآحاد في السلاسل. تقوم الخوارزمية بتبديل البتات حول، محاولة جعل السلاسل أكثر تمايزاً. الجزء "التابو" يعني أن الخوارزمية تحتفظ بذاكرة للحركات التي قامت بها للتو وترفض التراجع عنها فوراً، مما يجبرها على استكشاف مناطق جديدة بدلاً من الدوران في دوائر.

النتائج: 124 اكتشافاً جديداً

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

على سبيل المثال:

• بالنسبة لكود بطول 39 مع قيود محددة، كان الرقم القياسي السابق هو 1,014 كلمة. وجدت الطريقة الجديدة 1,118 كلمة. أي زيادة قدرها 104!
• لطول 40، قفز الرقم القياسي من 1,170 إلى 1,230.
• لطول 56، ارتفع العدد من 2,414 إلى 2,477.

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

أرقام التقبيل: أثر جانبي مفاجئ

هنا يصبح الأمر أكثر إثارة للاهتمام. تتطرق الورقة أيضاً إلى مفهوم أرقام التقبيل (kissing numbers). تخيل أن لديك كرة ضخمة في منتصف غرفة. كم عدد الكرات الأخرى من نفس الحجم التي يمكنك حشرها حول الكرة المركزية بحيث تلمس جميعها الكرة المركزية دون أن تتداخل مع بعضها البعض؟ في الفضاء ثلاثي الأبعاد، الإجابة هي 12. ولكن في الأبعاد الأعلى (مثل 32 أو 33 بعداً)، تكون الإجابة أصعب بكثير في العثور عليها.

الرياضيات الخاصة بأرقام التقبيل هذه مرتبطة بعمق بالأكواد ذات الوزن الثابت التي وجدها إيكولز. ولأن بحثه حسن الأكواد لمعايير محددة (تحديداً $A(n, 8, 8)$)، فقد حسن تلقائياً الحدود الدنيا لأرقام التقبيل في الأبعاد 32 و33 و34 و37.

على سبيل المثال، بالنسبة للبعد 32 ($\tau_{32}$)، كان التقدير السابق هو أنه يمكن لـ 345,408 كرة على الأقل أن تلمس الكرة المركزية. ومع الأكواد الجديدة، يقفز هذا الرقم إلى 346,432. إنها زيادة مئوية صغيرة، ولكن في عالم الهندسة عالية الأبعاد، يعد العث p على كرة واحدة إضافية تتسع هو انتصار كبير.

الخلاصة

لم يجد ويليام إيكولز مجرد أكواد أفضل فحسب؛ بل أظهر أنه من خلال كونك ذكياً في كيفية بدء بحثك — عبر استخدام "بذور" من المعرفة الموجودة بدلاً من البدء بشكل أعمى — يمكنك العثัง حلول أفضل بكثير. تثبت الورقة أن 124 تحسيناً محدداً أمر ممكن، وهي تعطينا أرضية جديدة أعلى لمقدار البيانات التي يمكننا حزمها بشكل موثوق في هذه السلاسل الرقمية. إنها تذكير بأن أفضل طريقة للمضي قدماً هي أحياناً الوقوف على أكتاف ما نعرفه بالفعل، بدلاً من محاولة بناء كل شيء من الصفر.