การค้นหาแบบแพร่กระจายแบบสุ่ม (SDS)ได้รับการอธิบายครั้งแรกในปี 1989 ในฐานะอัลกอริทึมการจับคู่รูปแบบ ตามประชากร ^{[ 1 ]}มันอยู่ในตระกูลของปัญญาแบบกลุ่มและการค้นหาและเพิ่มประสิทธิภาพที่ได้รับแรงบันดาลใจจากธรรมชาติ ซึ่งรวมถึงการเพิ่มประสิทธิภาพอาณานิคมมดการเพิ่มประสิทธิภาพฝูงอนุภาคและอัลกอริทึมทางพันธุกรรมดังนั้น SDS จึงเป็น เมตา ฮิวริสติกปัญญาแบบกลุ่ม ตัวแรก แตกต่างจาก การสื่อสารแบบ สติ๊กเมอร์เจติกที่ใช้ในการเพิ่มประสิทธิภาพอาณานิคมมดซึ่งขึ้นอยู่กับการปรับเปลี่ยนคุณสมบัติทางกายภาพของสภาพแวดล้อมจำลอง SDS ใช้รูปแบบการสื่อสารโดยตรง (หนึ่งต่อหนึ่ง) ระหว่างตัวแทนที่คล้ายกับกลไกการเรียกแบบคู่ขนานที่ใช้โดยมดสายพันธุ์หนึ่งLeptothorax acervorum

ในระบบ SDS เอเจนต์จะทำการประเมินสมมติฐาน (แนวทางแก้ปัญหาที่เป็นไปได้สำหรับปัญหาการค้นหา) บางส่วนและราคาประหยัด จากนั้นพวกเขาก็จะแบ่งปันข้อมูลเกี่ยวกับสมมติฐาน ( การแพร่กระจายข้อมูล) ผ่านการสื่อสารแบบตัวต่อตัวโดยตรง ผลจากกลไกการแพร่กระจายนี้ ทำให้สามารถระบุแนวทางแก้ปัญหาที่มีคุณภาพสูงได้จากกลุ่มของเอเจนต์ที่มีสมมติฐานเดียวกัน การทำงานของ SDS นั้นเข้าใจได้ง่ายที่สุดโดยใช้การเปรียบเทียบง่ายๆ คือ เกมร้านอาหาร

กลุ่มผู้แทนเข้าร่วมการประชุมระยะยาวในเมืองที่ไม่คุ้นเคย ทุกคืนผู้แทนแต่ละคนต้องหาที่รับประทานอาหาร มีร้านอาหารให้เลือกมากมาย แต่ละร้านมีอาหารหลากหลายประเภท ปัญหาที่กลุ่มนี้เผชิญคือการหาร้านอาหารที่ดีที่สุด นั่นคือร้านอาหารที่ผู้แทนจำนวนมากที่สุดจะเพลิดเพลินกับการรับประทานอาหาร แม้แต่การค้นหาแบบครบถ้วน พร้อมกัน ผ่านร้านอาหารและเมนูอาหารทั้งหมดก็ใช้เวลานานเกินไป เพื่อแก้ปัญหานี้ ผู้แทนจึงตัดสินใจใช้การค้นหาแบบสุ่มแพร่กระจาย (stochastic diffusion search)

ผู้แทนแต่ละคนทำหน้าที่เป็นตัวแทนที่ตั้งสมมติฐานว่าร้านอาหารที่ดีที่สุดในเมืองคือร้านใด ทุกคืนผู้แทนแต่ละคนจะทดสอบสมมติฐานของตนโดยการไปรับประทานอาหารที่ร้านนั้นและสุ่มเลือกเมนูอาหารหนึ่งอย่าง ในเช้าวันรุ่งขึ้นขณะรับประทานอาหารเช้า ผู้แทนทุกคนที่ไม่ได้ประทับใจกับอาหารในคืนก่อน จะขอให้เพื่อนร่วมงานที่สุ่มเลือกมาหนึ่งคนเล่าความประทับใจเกี่ยวกับอาหารเย็นของตนให้ฟัง หากประสบการณ์ดี เขาจะเลือกไปรับประทานอาหารที่ร้านนั้นเช่นกัน แต่ถ้าไม่ดี เขาจะสุ่มเลือกร้านอาหารอื่นจากรายชื่อในสมุดหน้าเหลือง การใช้กลยุทธ์นี้พบว่า ผู้แทนจำนวนมากจะมารวมตัวกันที่ร้านอาหาร 'ที่ดีที่สุด' ในเมืองอย่างรวดเร็ว

SDS ได้ถูกนำไปประยุกต์ใช้กับปัญหาที่หลากหลาย เช่นการค้นหาข้อความ [Bishop, 1989] การจดจำวัตถุ [Bishop, 1992] การติดตามคุณลักษณะ [Grech-Cini, 1993] การระบุตำแหน่งด้วยตนเอง ของหุ่นยนต์เคลื่อนที่ [Beattie, 1998] และการเลือกไซต์สำหรับเครือข่ายไร้สาย [Whitaker, 2002]

แตกต่างจากเทคนิคการค้นหาที่ได้รับแรงบันดาลใจจากธรรมชาติหลายๆ เทคนิค SDS มีกรอบทางคณิตศาสตร์ที่ครอบคลุมซึ่งอธิบายพฤติกรรมของมัน การวิเคราะห์ SDS ได้ตรวจสอบความเหมาะสมที่สุดและการลู่เข้า ในระดับสากล [Nasuto, 1998] ความซับซ้อนของเวลาเชิงเส้น[Nasuto et al., 1999] ความทนทาน [Myatt, 2004] และการจัดสรรทรัพยากร [Nasuto, 1999] ภายใต้เงื่อนไขการค้นหาที่หลากหลาย