نموذج NK

نموذج NK هو نموذج رياضي وصفه مخترعه الرئيسي ستيوارت كوفمان بأنه سطح لياقة "قابل للتعديل" . وتجسد عبارة "قابل للتعديل" فكرة إمكانية تعديل كل من الحجم الإجمالي لسطح اللياقة وعدد "التلال والوديان" المحلية فيه من خلال تغيير معياريه.${\displaystyle N}$و${\displaystyle K}$، مع${\displaystyle N}$كونه طول سلسلة من التطور و${\displaystyle K}$تحديد مستوى وعورة المناظر الطبيعية.

لقد وُظِّف نموذج NK في مجالاتٍ عديدة، منها الدراسات النظرية لعلم الأحياء التطوري ، وعلم المناعة ، والتحسين ، والتطور التكنولوجي ، وعلم الفريق، ^{[ 1 ]} والأنظمة المعقدة . كما اعتُمد النموذج في نظرية التنظيم ، حيث يُستخدم لوصف كيفية بحث كيانٍ ما في بيئةٍ ما من خلال التلاعب بخصائصه المختلفة. فعلى سبيل المثال، يمكن أن يكون الكيان منظمة ، وتمثل التلال والوديان الربح (أو تغيراته)، ويتطلب التحرك في البيئة قراراتٍ تنظيمية (مثل إضافة خطوط إنتاج أو تغيير الهيكل التنظيمي)، والتي تتفاعل فيما بينها وتؤثر على الربح بطريقةٍ معقدة. ^{[ 2 ]}

نسخة مبكرة من النموذج، والتي لم تأخذ في الاعتبار سوى الأكثر سلاسة (${\displaystyle K=0}$) والأكثر صلابة (${\displaystyle K=N-1}$تم تقديم مفهوم المناظر الطبيعية في كتاب كوفمان وليفين (1987). ^{[ 3 ]} أما النموذج كما هو معروف حاليًا فقد ظهر لأول مرة في كتاب كوفمان وواينبرغر (1989). ^{[ 4 ]}

أحد أسباب اكتساب هذا النموذج اهتمامًا واسعًا في مجال التحسين هو كونه حالةً بسيطةً للغاية لما يُعرف بمسألة NP-كاملة ^{[ 5 ]} ، ما يعني صعوبة إيجاد الحلول المثلى الشاملة. وقد أُثبت مؤخرًا أن نموذج NK لـ K > 1 هو أيضًا مسألة PLS-كاملة ^{[ 6 ]} ، ما يعني صعوبة إيجاد حتى الحلول المثلى المحلية للياقة البدنية. ولهذا الأمر تبعاتٌ على دراسة التطور المفتوح .

البلازميد عبارة عن حلقة صغيرة من الحمض النووي (DNA) داخل خلايا معينة ، ويمكنه التكاثر بشكل مستقل عن الخلايا المضيفة. لنفترض أننا نرغب في دراسة مدى كفاءة البلازميدات.

لتبسيط الأمر، نمثل البلازميد كحلقة من N جينًا محتملاً، مرتبة دائمًا بنفس الترتيب، ولكل منها حالتان محتملتان (نشط أو غير نشط، من النوع X أو من النوع Y، إلخ...). ثم يُنمذج البلازميد بسلسلة ثنائية طولها N ، وبالتالي تكون دالة اللياقة هي${\displaystyle F:\{0,1\}^{N}\to \mathbb {R} }$.

أبسط نموذج هو الذي لا تتفاعل فيه الجينات مع بعضها البعض، وبالتالي نحصل على$${\displaystyle F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1})+f_{2}(S_{2})+\cdots +f_{N}(S_{N})}$$حيث كل${\displaystyle f_{i}(S_{i})}$يشير إلى مساهمة الجين في اللياقة${\displaystyle S_{i}}$في الموقع${\displaystyle i}$.

لنمذجة التفاعل الجيني ، نُدخل عاملاً آخر K ، وهو عدد الجينات الأخرى التي يتفاعل معها جينٌ ما. من المعقول افتراض أنه على البلازميد، يتفاعل جينان إذا كانا متجاورين، مما يُعطي$${\displaystyle F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1},S_{2})+f_{2}(S_{2},S_{3})+\cdots +f_{N-1}(S_{N-1},S_{N})+f_{N}(S_{N},S_{1})}$$على سبيل المثال، عندما تكون K = 1 و N = 5 ،

${\displaystyle F(00101)=f_{1}(0,0)+f_{2}(0,1)+f_{3}(1,0)+f_{4}(0,1)+f_{5}(1,0)}$

يقوم نموذج NK بتعميم هذا من خلال السماح بقيم K و N المحدودة التعسفية، بالإضافة إلى السماح بتعريف تعسفي لتجاور الجينات (لا تقع الجينات بالضرورة على دائرة أو قطعة مستقيمة).

يُعرّف نموذج NK فضاءً طوريًا توافقيًا ، يتكون من كل سلسلة (مختارة من أبجدية معينة) بطول${\displaystyle N}$لكل سلسلة نصية في فضاء البحث هذا، يتم تحديد قيمة عددية (تُسمى الملاءمة ). إذا تم تحديد مقياس مسافة بين السلاسل النصية، فإن البنية الناتجة تُسمى مشهدًا .

تُحدد قيم اللياقة وفقًا للنسخة المحددة من النموذج، ولكن السمة الرئيسية لنموذج NK هي أن لياقة سلسلة معينة${\displaystyle S}$هو مجموع المساهمات من كل موضع${\displaystyle f_{i}(S)}$في السلسلة:

${\displaystyle F(S)=\sum _{i}{\tilde {f}}_{i}(S),}$

وتعتمد مساهمة كل موقع بشكل عام على حالته وحالة${\displaystyle K}$مواقع أخرى:

${\displaystyle {\tilde {f}}_{i}(S)=f_{i}(S_{i},S_{k_{i1}},\dots ,S_{k_{iK}}),}$

أين${\displaystyle k_{ij}}$هو فهرس${\displaystyle j}$الجار رقم 1 للموقع${\displaystyle i}$.

وبالتالي، فإن دالة اللياقة${\displaystyle f_{i}}$هي عبارة عن دالة تربط بين سلاسل طولها K  +  1 وقيم عددية، والتي يطلق عليها واينبرغر في أعماله اللاحقة اسم "مساهمات اللياقة". وغالبًا ما يتم اختيار مساهمات اللياقة هذه عشوائيًا من توزيع احتمالي محدد .

تتحكم قيمة K في درجة التفاعل الجيني (Epistasis) في نموذج NK، أو مدى تأثير المواقع الجينية الأخرى على مساهمة موقع جيني معين في اللياقة. عندما تكون K = 0، تكون لياقة سلسلة معينة عبارة عن مجموع بسيط لمساهمات المواقع الجينية الفردية: بالنسبة لدوال اللياقة غير التافهة، يوجد حل أمثل عالمي يسهل تحديده (مجموعة الأصفار إذا كانت f (0) > f (1)، أو مجموعة الآحاد إذا كانت f (1) > f (0)). أما عندما تكون K غير صفرية ، فإن لياقة السلسلة هي مجموع لياقات السلاسل الفرعية، والتي قد تتفاعل معًا لتُعيق النظام (انظر كيفية تحقيق اللياقة المثلى في المثال أعلاه). وبالتالي، فإن زيادة K تزيد من وعورة سطح اللياقة.

في عام 1991، نشر واينبرغر تحليلاً مفصلاً ^{[ 7 ]} للقضية التي${\displaystyle 1<<k\leq N}$ويتم اختيار مساهمات اللياقة عشوائيًا. وقد تبين لاحقًا أن تقديره التحليلي لعدد الحلول المثلى المحلية معيب . ومع ذلك، تدعم التجارب العددية المضمنة في تحليل واينبرغر نتيجته التحليلية القائلة بأن اللياقة المتوقعة لسلسلة ما تتوزع توزيعًا طبيعيًا بمتوسط ​​يقارب

${\displaystyle \mu +\sigma {\sqrt {{2\ln(k+1)} \over {k+1}}}}$

وتباين يقارب

${\displaystyle {{(k+1)\sigma ^{2}} \over {N[k+1+2(k+2)\ln(k+1)]}}}$.

لقد وجد نموذج NK استخدامًا في العديد من المجالات، بما في ذلك دراسة الزجاج المغزلي ، وحل المشكلات الجماعية ، ^{[ 8 ]} والتفاعل الجيني والتعددية في علم الأحياء التطوري ، والتحسين التوافقي .