Software evolution is critical to extending the utility and life of distributed real-time and embedded (DRE) systems.
Determining the optimal set of software and hardware components to evolve that (1) incorporate cutting-edge
technology and (2) satisfy DRE system resource constraints, such as memory, power, and CPU usage is an
NP-Hard problem. This article provides four contributions to evolving legacy DRE system configurations. First,
we present the Software Evolution Analysis with Resources (SEAR) technique for converting legacy DRE system
configurations, external resource availabilities, and candidate replacement components into multiple-choice multidimension
knapsack problems (MMKP). Second, we present a formal methodology for assessing the validity of
evolved system configurations. Third, we apply heuristic approximation algorithms to determine low-cost, high
value evolution paths in polynomial time. Finally, we analyze results of experiments that apply these techniques
to determine which technique is most effective for given system parameters. Our results show that constraint
solvers can only evolve small system configurations, whereas approximation techniques are needed to evolve
larger system configurations.