بناء تصميمات الكتل غير المكتملة المتوازنة (BIBDs) من خلال البحث في الجوار المقيد المتغير (VCNS) Construction of Balanced Incomplete Block Designs (BIBDs) through Variable Constrained Neighborhood Search (VCNS)

شارك:
المجلة: Boletim da Sociedade Paranaense de Matemática، المجلد: 44، العدد: 1
DOI: https://doi.org/10.5269/bspm.78042
تاريخ النشر: 2026-01-19
المؤلف: Pratibha Karki وآخرون
الموضوع الرئيسي: طرق تصميم التجارب المثلى

نظرة عامة

تتناول هذه الدراسة التحدي الحاسم المتمثل في مقارنة علاجات متعددة مع الأخذ في الاعتبار متغيرات واحدة أو متعددة، وهي قضية شائعة في مجالات مختلفة. على الرغم من أن الدراسات السابقة قد ركزت على تخصيص العلاج الأمثل باستخدام تصاميم عشوائية تمامًا استنادًا إلى معايير D- و A-optimality، إلا أنه كان هناك استكشاف محدود لهذه القضية ضمن إطار محجوز. لمواجهة ذلك، يقدم المؤلفون خوارزمية بحث تكرارية فعالة مصممة لتصاميم الكتل، مع توسيعها بشكل خاص لبناء تصاميم كتل غير مكتملة متوازنة (BIBDs).

الهدف الرئيسي من هذه الدراسة هو تنفيذ خوارزمية البحث في الجوار المقيد المتغير (VCNS) المقترحة لبناء BIBD وتقييم أدائها مقارنة بالخوارزميات الموجودة. تعتبر مساهمة كبيرة في هذا البحث هي تكييف خوارزمية VCNS مع سياق BIBD، مما يوفر أداة حسابية جديدة لا تحافظ فقط على أداء تنافسي ولكن أيضًا تقلل من المتطلبات الحسابية. يعزز هذا التقدم الأدبيات الموجودة من خلال تقديم منهجيات محسنة لتصاميم مقارنة العلاج الفعالة.

مقدمة

تناقش مقدمة الورقة تصاميم كتل غير مكتملة متوازنة (BIBDs)، والتي تعتبر هياكل تركيبية حاسمة تستخدم في مجالات مختلفة مثل تصميم التجارب، التحليل الإحصائي، والتحسين. يتم تعريف BIBD بواسطة المعلمات \(v\)، \(b\)، \(k\)، \(r\)، و\(\lambda\)، مما يضمن أن كل علاج يظهر في عدد محدد من الكتل وأن أزواج العلاجات تتواجد معًا في عدد محدد من الكتل. على الرغم من أهمية BIBDs في تقليل التحيزات وتعزيز كفاءة التجارب، فإن طرق البناء التقليدية، بما في ذلك التقنيات الجبرية والتحولات الدورية، غالبًا ما تفتقر إلى القابلية للتعميم والتطبيق العملي عبر مجموعات المعلمات المتنوعة.

لقد أدت التقدمات الأخيرة في التقنيات الحسابية إلى إدخال أساليب البرمجة المختلطة غير الخطية (MIP)، والتي، على الرغم من مرونتها، تواجه تحديات تتعلق بتكاليف حسابية عالية وأوقات معالجة طويلة لتصاميم كبيرة النطاق. للتغلب على هذه القيود، تم استكشاف الخوارزميات الهيورية والميتاهيرية، مثل الخوارزميات الجينية والتبريد المحاكي، على الرغم من أنها غالبًا ما تكافح مع الأمثل المحلية. تقترح الورقة استخدام بحث الجوار المتغير (VNS)، وهو ميتاهيرية تستكشف بشكل منهجي جوار الحلول لتجنب الركود وتعزيز كفاءة البحث. تهدف الدراسة إلى تطوير خوارزمية تعتمد على VNS لبناء BIBD، ومقارنة أدائها مع الطرق الموجودة لتوفير بديل قوي يعالج قيود الأساليب التقليدية والحسابية. توضح الأقسام التالية من الورقة صياغة المشكلة، تصميم التجربة، تطوير الخوارزمية، ومقارنة الأداء.

طرق

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

مناقشة

في هذه الدراسة، يقدم المؤلفون خوارزمية البحث في الجوار المقيد المتغير (VCNS) المصممة لبناء تصاميم كتل غير مكتملة متوازنة (BIBDs)، مع التركيز بشكل خاص على التكوينات المتماثلة. تتميز BIBDs بمعلمات محددة (v، b، r، k، λ) التي تحدد عدد العلاجات، الكتل، التكرارات، حجم الكتلة، والتوافق الثنائي. تعالج خوارزمية VCNS التعقيد التركيبي لبناء BIBD من خلال تأطيرها كمشكلة تحسين تركيبي مقيدة، مما يسمح بالاستكشاف الفعال لمصفوفات الحوادث الممكنة مع ضمان الامتثال لخصائص BIBD. تقوم الخوارزمية بتحسين تخصيصات العلاج بشكل تكراري لتلبية الشروط المطلوبة للتكرار والتوافق الثنائي، مما يظهر أداءً قويًا عبر توزيعات التهيئة المختلفة.

تشير النتائج إلى أن خوارزمية VCNS قد حلت بنجاح 10 من 11 حالة BIBD متماثلة معيارية، محققة معدل نجاح يبلغ 91%، وهو ما يقارن بأداء الخوارزميات الموجودة مثل البحث المحظور. يبرز هذا فعالية الخوارزمية في التغلب على قيود الأساليب التقليدية، خاصة في السيناريوهات التي تكون فيها الجدوى الحسابية مصدر قلق. تختتم الدراسة بأن خوارزمية VCNS لا توفر فقط حلاً قابلاً لبناء BIBDs صالحة ولكن لديها أيضًا تطبيقات محتملة في توليد تصاميم تركيبية أخرى، مما يمهد الطريق للبحوث المستقبلية في هذا المجال.

Journal: Boletim da Sociedade Paranaense de Matemática, Volume: 44, Issue: 1
DOI: https://doi.org/10.5269/bspm.78042
Publication Date: 2026-01-19
Author(s): Pratibha Karki et al.
Primary Topic: Optimal Experimental Design Methods

Overview

The research addresses the critical challenge of comparing multiple treatments while accounting for single or multiple covariates, a concern prevalent in various fields. Although previous studies have focused on optimal treatment allocation using completely randomized designs based on D- and A-optimality criteria, there has been limited exploration of this issue within a blocked framework. To tackle this, the authors introduce an efficient iterative search algorithm tailored for block designs, specifically extending it to construct Balanced Incomplete Block Designs (BIBDs).

The primary aim of this study is to implement the proposed Variable Constrained Neighborhood Search (VCNS) algorithm for BIBD construction and to evaluate its performance against existing algorithms. A significant contribution of this research is the adaptation of the VCNS algorithm to the BIBD context, providing a new computational tool that not only maintains competitive performance but also reduces computational demands. This advancement enhances the existing literature by offering improved methodologies for efficient treatment comparison designs.

Introduction

The introduction of the paper discusses Balanced Incomplete Block Designs (BIBDs), which are crucial combinatorial structures utilized in various fields such as experimental design, statistical analysis, and optimization. A BIBD is defined by parameters \(v\), \(b\), \(k\), \(r\), and \(\lambda\), ensuring that each treatment appears in a specified number of blocks and that treatment pairs co-occur in a defined number of blocks. Despite the significance of BIBDs in reducing biases and enhancing experimental efficiency, traditional construction methods, including algebraic techniques and cyclic shifts, often lack generalizability and practical applicability across diverse parameter sets.

Recent advancements in computational techniques have introduced nonlinear mixed-integer programming (MIP) approaches, which, while flexible, face challenges related to high computational costs and extensive processing times for large-scale designs. To overcome these limitations, heuristic and metaheuristic algorithms, such as genetic algorithms and simulated annealing, have been explored, although they often struggle with local optima. The paper proposes the use of Variable Neighborhood Search (VNS), a metaheuristic that systematically explores solution neighborhoods to avoid stagnation and enhance search efficiency. The study aims to develop a VNS-based algorithm for BIBD construction, comparing its performance with existing methods to provide a robust alternative that addresses the limitations of traditional and computational approaches. The subsequent sections of the paper outline the problem formulation, experimental design, algorithm development, and performance comparison.

Methods

In the methods section, the authors emphasize the importance of selecting an effective initial allocation design for experimental units, as it significantly influences the convergence speed toward an optimal solution. They highlight that a suboptimal initial design can result in unfavorable final outcomes. To mitigate this risk, the authors adopt a re-randomization strategy, as proposed in previous literature, which involves generating ten randomized initial designs and subsequently selecting the one that yields the most favorable preliminary criterion value. This approach, referenced in studies [19] and [20], enhances the robustness and reliability of the allocation process.

Discussion

In this study, the authors present a Variable Constrained Neighborhood Search (VCNS) algorithm designed for constructing Balanced Incomplete Block Designs (BIBDs), particularly focusing on symmetric configurations. BIBDs are characterized by specific parameters (v, b, r, k, λ) that dictate the number of treatments, blocks, replications, block size, and pairwise concurrence. The VCNS algorithm addresses the combinatorial complexity of BIBD construction by framing it as a constrained combinatorial optimization problem, allowing for efficient exploration of feasible incidence matrices while ensuring compliance with BIBD properties. The algorithm iteratively refines treatment allocations to meet the required conditions of replication and pairwise concurrence, demonstrating robust performance across various initialization distributions.

The results indicate that the VCNS algorithm successfully solved 10 out of 11 benchmark symmetric BIBD instances, achieving a 91% success rate, comparable to the performance of existing algorithms such as Tabu Search. This highlights the algorithm’s effectiveness in overcoming the limitations of traditional methods, particularly in scenarios where computational feasibility is a concern. The study concludes that the VCNS algorithm not only provides a viable solution for constructing valid BIBDs but also has potential applications in generating other combinatorial designs, paving the way for future research in this domain.