Random Chemistry (RC)
This is a bare-bones implementation of the 'Random Chemistry' (RC) algorithm for finding a defective set from a universal set of N elements in log(N) trials. Multiple calls to this function comprise statistically independent trials.
Included with the algorithm implementation are a dummy fitness function and 'defective sets' to test the algorithm. See the accompanying algorithm, 'Sampling Inspired by Group Hyperedge Testing' (SIGHT), which can also be used to find defective sets in log(N) trials. SIGHT uses the same dummy fitness function and defective sets, for easy comparison, and is available on the File Exchange at: https://www.mathworks.com/matlabcentral/fileexchange/72718-sampling-inspired-by-group-hyperedge-testing-sight. Both algorithms have been successfully applied to identify small sets of transmission lines whose simultaneous failures cause cascading blackouts in power grid simulations (see reference below).
DISCLAIMER: This implementation is designed to be easy to read and understand, but is NOT optimized for efficiency and omits all the book-keeping and options under development that are contained in our working code. This should really be viewed as readable pseudo-code that runs.
COPYRIGHT: Laurence A. Clarfeld and Margaret J. Eppstein, Department of Computer Science, Univ. of Vermont
DATE: 8/26/2019
You are free to use or modify this code for research purposes, as long as you reference the website where you obtained the code.
IF YOU PUBLISH ANYTHING USING THIS CODE OR ALGORITHM, PLEASE REFERENCE THE FOLLOWING PAPERS:
1. Eppstein, Margaret J., and Paul DH Hines. "A “random chemistry” algorithm for identifying collections of multiple contingencies that initiate cascading failure." IEEE Transactions on Power Systems 27.3 (2012): 1698-1705.
2. Rezaei, Pooya, Margaret J. Eppstein, and Paul DH Hines. "Rapid Assessment, Visualization, and Mitigation of Cascading Failure Risk in Power Systems." System Sciences (HICSS), 2015 48th Hawaii International Conference on. IEEE, 2015.
3. Clarfeld, L.A., and Eppstein, M.J. "Group-Testing on Hypergraphs with Variable-Cost Tests: A Power Systems Case Study", arXiv:1909.04513 [physics.soc-ph] (Preprint). September 9, 2019. Available from: https://arxiv.org/abs/1909.04513
Citar como
Eppstein, Margaret J., and Paul DH Hines. "A “random chemistry” algorithm for identifying collections of multiple contingencies that initiate cascading failure." IEEE Transactions on Power Systems 27.3 (2012): 1698-1705.
Rezaei, Pooya, Margaret J. Eppstein, and Paul DH Hines. "Rapid Assessment, Visualization, and Mitigation of Cascading Failure Risk in Power Systems." System Sciences (HICSS), 2015 48th Hawaii International Conference on. IEEE, 2015.
Clarfeld, L.A., and Eppstein, M.J. "Group-Testing on Hypergraphs with Variable-Cost Tests: A Power Systems Case Study", arXiv:1909.04513 [physics.soc-ph] (Preprint). September 9, 2019. Available from: https://arxiv.org/abs/1909.04513
Compatibilidad con la versión de MATLAB
Compatibilidad con las plataformas
Windows macOS LinuxCategorías
Etiquetas
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Descubra Live Editor
Cree scripts con código, salida y texto formateado en un documento ejecutable.