下载文档原格式
constraint的粒子群算法python 粒子群算法(Particle Swarm Optimization, PSO)是一种启发式的优化算法，灵感来源于鸟群或鱼群的群体行为。
该算法通过模拟鸟群或鱼群中个体的行为来寻找最优解。
在算法的实现中，每个解都被称为一个粒子，粒子通过在解空间中搜索来优化目标函数。
在使用粒子群算法求解约束优化问题时，我们需要注意下面几点：1.约束的表示方式：约束条件可以通过不等式或等式来表示。
不等式约束一般采用罚函数(Penalty Function)或约束处理法(Constraint Handling Approach)来处理。
罚函数通过将违反约束条件的解进行惩罚，将其转化为受约束问题。
约束处理法是通过调整粒子在搜索空间中的位置来保证解满足约束条件。
等式约束则可以通过拉格朗日乘子法或者惩罚函数法进行处理。
2.粒子的编码方式：粒子的编码方式决定了搜索空间的范围。
对于连续变量的约束优化问题，可以使用实数编码或者二进制编码。
实数编码将变量的取值范围映射到实数域，通过调整实数值来搜索解空间。
二进制编码则将变量的取值范围离散为一定精度的二进制串。
对于离散变量的约束问题，可以使用整数编码或者排列编码。
3.约束处理方法：在粒子更新过程中，需要考虑每个粒子是否满足约束条件。
对于不满足约束条件的粒子，可以通过引入惩罚项或者调整粒子的位置来保证解满足约束条件。
惩罚函数法是一种常用的处理约束的方法，通过在目标函数中引入罚项来惩罚违反约束的解。
调整粒子的位置可以通过投影法或者边界法来实现。
4.适应度函数的设计：适应度函数的设计在粒子群算法中起到至关重要的作用。
适应度函数应该综合考虑目标函数和约束条件对解的影响。
对于约束优化问题，适应度函数可以通过将违反约束的解进行惩罚或者调整位置来处理。
下面是一个简单的示例，展示如何使用粒子群算法求解带约束的优化问题的Python代码：```pythonimport numpy as npclass Particle:def __init__(self, num_variables, min_values, max_values): self.position = np.random.uniform(min_values, max_values, num_variables)self.velocity = np.random.uniform(-1, 1, num_variables)self.best_position = self.position.copy()self.best_fitness = Nonedef update_velocity(self, global_best_position, w, c1,c2):self.velocity = w * self.velocity + c1 * np.random.rand() * (self.best_position - self.position) + c2 * np.random.rand() * (global_best_position - self.position)def update_position(self):self.position += self.velocitydef evaluate_fitness(self, objective_func,constraint_func):self.fitness = objective_func(self.position)if constraint_func(self.position):self.fitness += 10000 # Penalty for violating constraintsif self.best_fitness is None or self.fitness <self.best_fitness:self.best_fitness = self.fitnessself.best_position = self.position.copy()def particle_swarm_optimization(num_particles,num_variables, min_values, max_values, objective_func, constraint_func, max_iterations=100, w=0.729, c1=1.49445, c2=1.49445):particles = [Particle(num_variables, min_values,max_values) for _ in range(num_particles)]global_best_position = Noneglobal_best_fitness = Nonefor _ in range(max_iterations):for particle in particles:particle.update_velocity(global_best_position, w, c1, c2) particle.update_position()particle.evaluate_fitness(objective_func, constraint_func) if global_best_fitness is None or particle.best_fitness < global_best_fitness:global_best_fitness = particle.best_fitnessglobal_best_position = particle.best_position.copy()return global_best_position, global_best_fitness#定义目标函数和约束函数def objective_func(x):return x[0]**2 + x[1]**2def constraint_func(x):if x[0] + x[1] >= 1:return Trueelse:return False#设置问题参数和算法参数num_particles = 20num_variables = 2min_values = np.array([-5, -5])max_values = np.array([5, 5])max_iterations = 100#运行粒子群算法best_position, best_fitness =particle_swarm_optimization(num_particles, num_variables,min_values, max_values, objective_func, constraint_func, max_iterations)#打印结果print("Best position: ", best_position)print("Best fitness: ", best_fitness)```以上代码简单地实现了一个粒子群算法，并解决了一个带约束的优化问题。
[ Viewing Hints ] [ Book Home Page ] [ Free Newsletter ][ Seminars ] [ Seminars on CD ROM ] [ Consulting ]Annotated Solution GuideRevision 1.0for Thinking in C++, 2nd edition, Volume 1by Chuck Allison©2001 MindView, Inc. All Rights Reserved.[ Previous Chapter ] [ Table of Contents ] [ Next Chapter ] Chapter 1414-1Modify Car.cpp so that it also inherits from a class called Vehicle, placing appropriate member functions in Vehicle (that is, make up some member functions). Add a nondefault constructor to Vehicle, which you must call inside Car’s constructor.14-2Create two classes, A and B,with default constructors that announce themselves. Inherit a new class called C from A, and create a member object of B in C, but do not create a constructor for C. Create an object of class C and observe the results.14-3Create two classes, A and B,with default constructors that announce themselves. Inherit a new class called C from A, and create a member object of B in C, but do not create a constructor for C. Create an object of class C and observe the results.Solution://: S14:DefaultConstruction.cpp #include <iostream>using namespace std;class A {public:A() {cout << "A::A()\n";} };class B {public:B() {cout << "B::B()\n";} };class C : public A {B b;};int main() {C c;}/* Output:A::A()B::B()*////:~The “parts” of a C object are automatically constructed, inherited sub-objects first, followed by contained objects.14-4Create a three-level hierarchy of classes with default constructors, along with destructors, both of which announce themselves to cout. Verify that for an object of the most derived type, all three constructors and destructors are automatically called. Explain the order in which the calls are made.Solution://: S14:HierarchyConstruction.cpp#include <iostream>using namespace std;class A {public:A() {cout << "A::A()\n";}~A() {cout << "A::~A()\n";}};class B : public A {public:B() {cout << "B::B()\n";}~B() {cout << "B::~B()\n";} };class C : public B {public:C() {cout << "C::C()\n";}~C() {cout << "C::~C()\n";} };int main() {C c;}/* Output:A::A()B::B()C::C()C::~C()B::~B()A::~A()*////:~An object’s “parts” are always constructed be fore the object itself. Applying this principle recursively requires that the sub-object at the top of the hierarchy must be created first. Destruction is always the reverse order of construction.(Exercises 14-5 through 14-8 are left to the reader.)14-5In Combined.cpp, create a class D that inherits from B and has a member object of class C. Add code to show when the constructors and destructors are being called.14-6Modify Order.cpp to add another level of inheritance Derived3 with member objects of class Member4 and Member5. Trace the output of the program.14-7In NameHiding.cpp, verify that in Derived2, Derived3, and Derived4, none of the base-class versions of f( ) are available.14-8Modify NameHiding.cpp by adding three overloaded functions named h( ) to Base, and show that redefining one of them in a derived class hides the others.14-9Inherit a class StringVector from vector<void*> and redefine the push_back( ) and operator[] member functions to accept and produce string*. What happens if you try to push_back( ) a void*?Solution://: S14:StringVector.cpp//{-msc} VC++ only fakes reinterpret_cast#include <iostream>#include <vector>#include <string>#include <cstddef> // For size_tusing namespace std;class StringVector : public vector<void*> {public:void push_back(string* s) {vector<void*>::push_back(s);}string*& operator[](size_t n) {return reinterpret_cast<string*>(vector<void*>::operator[](n));}const string* operator[](size_t n) const {return reinterpret_cast<const string*>(vector<void*>::operator[](n));}};int main() {StringVector v;string s1("live"), s2("long"), s3("and"), s4("prosper");v.push_back(&s1);v.push_back(&s2);v.push_back(&s3);v.push_back(&s4);for (size_t i = 0; i < v.size(); ++i)cout << *v[i] << endl;// void* p = &s1;// v.push_back(p); // error}/* Output:livelongandprosper*////:~The problem with the commented-out push_back( ) above is that there is no implicit conversion from a void* to any other type, as there is in C. This makes StringVector type-safe. Note that I overloaded both versions of operator[] (const and non-const).If you’ve done any amount of reading on object-oriented programming in C++, you probably have learned that you should never override a non-virtual function from a publicly-inherited class (see for example, Scott Meyers “Effective C++”, Item 37). The s tandard containers such as vector have no virtual functions at all, so there must be a better way to define StringVector. The Better Way is to use private inheritance, and provide access to the inherited functions as the following version illustrates.class StringVector : private vector<void*> {public:void push_back(string* s) {vector<void*>::push_back(s);}string*& operator[](size_t n) {return reinterpret_cast<string*>(vector<void*>::operator[](n));}const string* operator[](size_t n) const {return reinterpret_cast<const string*>(vector<void*>::operator[](n));}using vector<void*>::size;};Private inheritance combined with templates makes building such type-safe containers fairly simple. (See Chapter 16 and V olume 2).(Exercises 14-10 through 14-13 are left to the reader.)14-10Write a class containing a long and use the psuedo-constructor call syntax in the constructor to initialize the long.14-11Create a class called Asteroid. Use inheritance to specialize the PStash class in Chapter 13 (PStash.h & PStash.cpp) so that it accepts and returns Asteroid pointers. Also modify PStashTest.cpp to test your classes. Change the class so PStash is a member object.14-12Repeat Exercise 11 with a vector instead of a PStash.14-13In SynthesizedFunctions.cpp, modify Chess to give it a default constructor, copy-constructor, and assignment operator. Demonstrate that you’ve written these co rrectly.14-14Create two classes called Traveler and Pager without default constructors, but with constructors that take an argument of type string, which they simply copy to an internal string variable. For each class, write the correct copy-constructor and assignment operator. Now inherit a class BusinessTraveler from Traveler and give it a member object of type Pager. Write the correct default constructor, a constructor that takes a string argument, a copy-constructor, and an assignment operator.Solution://: S14:BusinessTraveler.cpp#include <iostream>#include <string>using namespace std;class Traveler {string str;public:Traveler(const string& s) : str(s) {}Traveler(const Traveler& t) : str(t.str) {}Traveler& operator=(const Traveler& t) { if (this != &t)str = t.str;return *this;}string getString() const {return str;}};class Pager {string str;public:Pager(const string& s) : str(s) {}Pager(const Pager& p) : str(p.str) {}Pager& operator=(const Pager& p) {if (this != &p)str = p.str;return *this;}string getString() const {return str;}};class BusinessTraveler : public Traveler {Pager pager;public:BusinessTraveler() : Traveler(""), pager("") {}BusinessTraveler(const string& t, const string& p): Traveler(t), pager(p) {}BusinessTraveler(const BusinessTraveler& b): Traveler(b), pager(b.pager) {}BusinessTraveler& operator=(const BusinessTraveler& b) { if (this != &b) {Traveler::operator=(b); // Assign base partpager = b.pager; // Assign derived part }return *this;}friend ostream& operator<<(ostream& os,const BusinessTraveler& b) { return os << "{\"" << b.getString() << "\", \""<< b.pager.getString() << "\"}";}};int main() {BusinessTraveler b1("Joe BusinessMan", "Pager 1");cout << b1 << endl;BusinessTraveler b2("Jane BusinessWoman", "Pager 2");cout << b2 << endl;BusinessTraveler b3;cout << b3 << endl;BusinessTraveler b4(b1);cout << b4 << endl;b3 = b2;cout << b3 << endl;}/* Output:{"Joe BusinessMan", "Pager 1"}{"Jane BusinessWoman", "Pager 2"}{"", ""}{"Joe BusinessMan", "Pager 1"}{"Jane BusinessWoman", "Pager 2"}*////:~The solution is a little clearer if BusinessTraveler has a constructor that takes two arguments: one for the Traveler’s name and one for the Pager name. The key point of this exercise is to get the constructor and assignment operator correct with inheritance. Both need to make sure that the base class sub-object is taken care of (which is sometimes easy to forget!). In constructors you use the initializer list; in assignment operators you explicitly call the base class assignment operator (since the base class data is private, you have no choice).14-15Create a class with two static member functions. Inherit from this class and redefine one of the member functions. Show that the other is hidden in the derived class.Solution://: S14:StaticBaseMethods.cpp#include <iostream>using namespace std;class Base {public:static void f() {cout << "Base::f()\n";}static void g() {cout << "Base::g()\n";}};class Derived : public Base {public:static void g(int) {cout << "Derived::g(int)\n";}};int main() {Derived::f();Derived::g(1);// Derived::g(); // Error: too few parameters }/* Output:Base::f()Derived::g(int)*////:~The fact that I introduced a parameter for g( ) in Derived is not significant; any function named the same as one in any base class hides all overloaded functions of the same name in the base classes (because derived classes constitute a nested scope).14-16Look up more of the member functions for ifstream. In FName2.cpp, try them out on the file object.(Left to the reader)14-17Use private and protected inheritance to create two new classes from a base class. Then attempt to upcast objects of the derived class to the base class. Explain what happens.Solution://: S14:InaccessibleBase.cpp//=***************************************!class Base {};class Private : private Base {};class Protected : protected Base {};int main() {Private pri;Protected pro;// Both statements are errors:Base* b = static_cast<Base*>(&pri);b = static_cast<Base*>(&pro);}/* Output:Error Line 12: Cannot cast from 'Private *' to 'Base *' in function main() Error Line 13: Cannot cast from 'Protected *' to 'Base *' in function main()*////:~Just like you can’t access private or protected members in non-member or non-derived contexts (respectively), neither can you attempt an upcast to a private or protected base class. These types of inheritance are used for implementation only, therefore, clients that only have the public interface available have no such access.14-18In Protected.cpp, add a member function in Derived that calls the protected Base memberread( ).(Left to the reader.)14-19Change Protected.cpp so that Derived is using protected inheritance. See if you can call value( ) for a Derived object.(Left to the reader.)14-20Create a class called SpaceShip with a fly( ) method. Inherit Shuttle from SpaceShip and add a land( ) method. Create a new Shuttle, upcast by pointer or reference to a SpaceShip, and try to call the land( ) method. Explain the results.Solution://: S14:NarrowingCast.cpp//=************************************!class SpaceShip {public:void fly() {}};class Shuttle : public SpaceShip {public:void land() {}};int main() {Shuttle shut;SpaceShip& ship = static_cast<SpaceShip&>(shut);nd(); // Error}/* Output:Error Line 16: 'land' is not a member of 'SpaceShip' in function main()*////:~No mystery here. The variable ship is a SpaceShip, which does not have a land( ) method. If SpaceShip had a land method, there would still be a problem: SpaceShip::land( ) would be called instead of Shuttle::land( ) (rarely the right thing to do!). This mystery is solved in the next chapter (read about virtual functions).(Exercises 14-21 through 14-25 are left to the reader.)14-21Modify Instrument.cpp to add a prepare( ) method to Instrument. Call prepare( ) inside tune( ). 14-22Modify Instrument.cpp so that play( ) prints a message to cout, and Wind redefines play( ) to print a different message to cout. Run the program and explain wh y you probably wouldn’t want this behavior. Now put the virtual keyword (which you will learn about in Chapter 15) in front of the play( ) declaration in Instrument and observe the change in the behavior.14-23In CopyConstructor.cpp, inherit a new class from Child and give it a Member m. Write a properconstructor, copy-constructor, operator=, and operator<< for ostreams, and test the class in main( ).14-24Take the example CopyConstructor.cpp and modify it by adding your own copy-constructor to Child without calling the base-class copy-constructor and see what happens. Fix the problem by making a proper explicit call to the base-class copy constructor in the constructor-initializer list of the Child copy-constructor.14-25Modify InheritStack2.cpp to use a vector<string>instead of a Stack.14-26Create a class Rock with a default constructor, a copy-constructor, an assignment operator, and a destructor, all of which announce to cout that they’ve been called. In main( ), create avector<Rock> (that is, hold Rock objects by value) and add some Rock s. Run the program and explain the output you get. Note whether the destructors are called for the Rock objects in the vector. Now repeat the exercise with a vector<Rock*>. Is it possible to create a vector<Rock&>?Solution://: S14:LikeARock.cpp#include <iostream>#include <vector>using namespace std;class Rock {public:Rock() {cout << "Rock()\n";}Rock(const Rock&) {cout << "Rock(const Rock&)\n";}Rock& operator=(const Rock&) {cout << "Rock()\n";return *this;}~Rock() {cout << "~Rock()\n";} };int main() {vector<Rock> byValue;Rock r1, r2, r3;byValue.push_back(r1);byValue.push_back(r2);byValue.push_back(r3);cout << "byValue populated\n\n";vector<Rock*> byPtr;byPtr.push_back(&r1);byPtr.push_back(&r2);byPtr.push_back(&r3);cout << "byPtr populated\n\n"; }/* Output:Rock()Rock()Rock()Rock(const Rock&)Rock(const Rock&)Rock(const Rock&)byValue populatedbyPtr populated~Rock()~Rock()~Rock()~Rock()~Rock()~Rock()*////:~All the standard C++ containers store a copy of their elements (hence the calls to the copy constructor above). Even byPtr stores copies; they’re just co pies of the pointers you sent topush_back( ). As you can also see, the destructor of byValue ensures that all its elements (copies) are destroyed. (Again, so does byPtr; pointers just don’t have destructors, so you see no trace output). It makes no sense to have a vector of references, since vectors store copies. If you store heap pointers in a container, you are responsible to delete them.14-27This exercise creates the design pattern called proxy. Start with a base class Subject and give it three functions: f( ), g( ), and h( ). Now inherit a class Proxy and two classes Implementation1 and Implementation2 from Subject. Proxy should contain a pointer to a Subject, and all the member functions for Proxy should just turn around and make the same calls through the Subject pointer. The Proxy constructor takes a pointer to a Subject that is installed in the Proxy(usually by the constructor). In main( ), create two different Proxy objects that use the two different implementations. Now modify Proxy so that you can dynamically change implementations.Solution:This is the well-known Proxy pattern from the Gang of Four (see "Design Patterns", Gamma et al, Prentice-Hall, 1994). Here's a solution that allows changing the implementation at run-time://: S14:Proxy.cpp#include <iostream>using namespace std;class Subject {public:virtual void f() = 0;virtual void g() = 0;virtual void h() = 0;};class Proxy : public Subject {Subject* pSubject;public:Proxy(Subject* pSubject = 0) {this->pSubject = pSubject;}void setSubject(Subject* pSubject) {this->pSubject = pSubject;}void f() {pSubject->f();}void g() {pSubject->g();}void h() {pSubject->h();}};class Implementation1 : public Subject { public:void f() {cout << "Implementation1::f\n";}void g() {cout << "Implementation1::g\n"; }void h() {cout << "Implementation1::h\n"; }};class Implementation2 : public Subject { public:void f() {cout << "Implementation2::f\n";}void g() {cout << "Implementation2::g\n";}void h() {cout << "Implementation2::h\n"; }};int main() {Implementation1 impl1;Proxy proxy(&impl1);proxy.f();proxy.g();proxy.h();Implementation2 impl2;proxy.setSubject(&impl2); proxy.f();proxy.g();proxy.h();} ///:~Here is the output:Implementation1::f Implementation1::gImplementation1::hImplementation2::fImplementation2::gImplementation2::hThe Subject class is typically an abstract class, since it represents the interface of the functionality you want. The Implementation classes provide different implementations of the interface, of course. The proxy class also must formally implement the interface, since it is the primary object type the client uses. The flexibility of this pattern comes from the ability to change implementations without changing which object the client uses (yet another instance of the principle: “All problems can be solved by introducing another level of indirection”). This is ac ommon technique to allow an object to “change colors” during its lifetime.14-28Modify ArrayOperatorNew.cpp from Chapter 13 to show that, if you inherit from Widget, the allocation still works correctly. Explain why inheritance in Framis.cpp from Chapter 13 would not work correctly.(Left to the reader)14-29Modify Framis.cpp from Chapter 13 by inheriting from Framis and creating new versions of new and delete for your derived class. Demonstrate that they work correctly.(Left to the reader)[ Previous Chapter ] [ Table of Contents ] [ Next Chapter ]Last Update:06/27/2002。
Sparse Solution of Underdetermined Linear Equationsby Stagewise Orthogonal Matching PursuitDavid L.Donoho1,Yaakov Tsaig2,Iddo Drori1,Jean-Luc Starck3March2006AbstractFinding the sparsest solution to underdetermined systems of linear equations y=Φx is NP-hard in general.We show here that for systems with‘typical’/‘random’Φ,a good approximation to thesparsest solution is obtained by applying afixed number of standard operations from linear algebra.Our proposal,Stagewise Orthogonal Matching Pursuit(StOMP),successively transforms the signal into a negligible residual.Starting with initial residual r0=y,at the s-th stage it formsthe‘matchedfilter’ΦT r s−1,identifies all coordinates with amplitudes exceeding a specially-chosenthreshold,solves a least-squares problem using the selected coordinates,and subtracts the least-squaresfit,producing a new residual.After afixed number of stages(e.g.10),it stops.In contrastto Orthogonal Matching Pursuit(OMP),many coefficients can enter the model at each stage inStOMP while only one enters per stage in OMP;and StOMP takes afixed number of stages(e.g.10),while OMP can take many(e.g.n).StOMP runs much faster than competing proposals for sparsesolutions,such as 1minimization and OMP,and so is attractive for solving large-scale problems.We use phase diagrams to compare algorithm performance.The problem of recovering a k-sparse vector x0from(y,Φ)whereΦis random n×N and y=Φx0is represented by a point(n/N,k/n)in this diagram;here the interesting range is k<n<N.For n large,StOMP correctly recovers(anapproximation to)the sparsest solution of y=Φx over a region of the sparsity/indeterminacy planecomparable to the region where 1minimization is successful.In fact,StOMP outperforms both 1minimization and OMP for extremely underdetermined problems.We rigorously derive a conditioned Gaussian distribution for the matchedfiltering coefficients at each stage of the procedure and rigorously establish a large-system limit for the performancevariables of StOMP.We precisely calculate large-sample phase transitions;these provide asymptot-ically precise limits on the number of samples needed for approximate recovery of a sparse vector byStOMP.We give numerical examples showing that StOMP rapidly and reliablyfinds sparse solutions in compressed sensing,decoding of error-correcting codes,and overcomplete representation.Keywords:compressed sensing,decoding error-correcting codes,sparse overcomplete representation. phase transition,large-system limit.random matrix theory.Gaussian approximation. 1minimization. stepwise regression.thresholding,false discovery rate,false alarm rate.MIMO channel,mutual access interference,successive interference cancellation.iterative decoding.Acknowledgements This work was supported by grants from NIH,ONR-MURI,a DARPA BAA, and NSF DMS00-77261,DMS01-40698(FRG)and DMS05-05303.1:Department of Statistics,Stanford University,Stanford CA,943052:Institute for Computational Mathematics in Engineering,Stanford University,Stanford CA,94305 3:DAPNIA/SEDI-SAP,Service d’Astrophysique,Centre Europeen d’Astronomie/Saclay,F-91191Gif-sur-Yvette Cedex France.1IntroductionThe possibility of exploiting sparsity in signal processing is attracting growing attention.Over the years, several applications have been found where signals of interest have sparse representations and exploiting this sparsity offers striking benefits;see for example[11,28,26,25,7].At the ICASSP2005conference a special session addressed the theme of exploiting sparsity,and a recent international workshop,SPARS05, was largely devoted to this topic.Very recently,considerable attention has focused on the following Sparse Solutions Problem(SSP). We are given an n×N matrixΦwhich is in some sense‘random’,for example a matrix with iid Gaussian entries.We are also given an n-vector y and we know that y=Φx0where x0is an unknown sparse vector.We wish to recover x0;however,crucially,n<N,the system of equations is underdetermined and so of course,this is not a properly-stated problem in linear algebra.Nevertheless,sparsity of x0is a powerful property that sometimes allows unique solutions.Applications areas for which this model is relevant include:App1:Compressed Sensing.x0represents the coefficients of a signal or image in a known basis which happens to sparsely represent that signal or image.Φencodes a measurement operator,i.e.an operator yielding linear combinations of the underlying object.Here n<N means that we collect fewer data than unknowns.Despite the indeterminacy,sparsity of x0allows for accurate recon-struction of the object from what would naively seem to be‘too few samples’[17,8,48].App2:Error rmation is transmitted in a coded block in which a small fraction of the entries may be corrupted.From the received data,one constructs a system y=Φx0;here x0 represents the values of errors which must be identifed/corrected,y represents(generalized)check sums,andΦrepresents a generalized checksum operator.It is assumed that the number of errors is smaller than a threshold,and so x0is sparse.This sparsity allows to perfectly correct the gross errors[9,48,28].App3:Sparse Overcomplete Representation.x0represents the synthesis coefficients of a signal y,which is assumed to be sparsely represented from terms in an overcomplete expansion;those terms are the columns ofΦ.The sparsity allows to recover a unique representation using only a few terms, despite the fact that representation is in general nonunique[43,11,21,20,50,51].In these applications,several algorithms are available to pursue sparse solutions;in some cases attractive theoretical results are known,guaranteeing that the solutions found are the sparsest possible solutions. For example,consider the algorithm of 1minimization,whichfinds the solution to y=Φx having minimal 1norm.Also called Basis Pursuit(BP)[11],this method enjoys some particularly striking theoretical properties,such as rigorous proofs of exact reconstruction under seemingly quite general circumstances[21,35,32,7,16,8,17,18]Unfortunately,some of the most powerful theoretical results are associated with fairly heavy com-putationally burdens.The research reported here began when,in applying the theory of compressed sensing to NMR spectroscopy,we found that a straightforward application of the 1minimization ideas in[17,58]required several days solution time per(multidimensional)spectrum.This seemed prohibitive computational expense to us,even though computer time is relatively less precious than spectrometer time.In fact,numerous researchers have claimed that general-purpose 1minimization is much too slow for large-scale applications.Some have advocated a heuristic approach,Orthogonal Matching Pursuit (OMP),(also called greedy approximation and stepwise regression in otherfields)[43,52,53,55,54], which though often effective in empirical work,does not offer the strong theoretical guarantees that attach to 1minimization.(For other heuristic approaches,see[50,51,29].)In this paper we describe Stagewise Orthogonal Matching Pursuit(StOMP),a method for approx-imate sparse solution of underdetermined systems with the property either thatΦis‘random’or that the nonzeros in x0are randomly located,or both.StOMP is significantly faster than the earlier methods BP and OMP on large-scale problems with sparse solutions.Moreover,StOMP permits a theoretical analysis showing that StOMP is similarly succcessful to BP atfinding sparse solutions.Our analysis uses the notion of comparison of phase transitions as a performance metric.We con-sider the phase diagram,a2D graphic with coordinates measuring the relative sparsity of x0(numberof nonzeros in x0/number of rows inΦ),as well as the indeterminacy of the system y=Φx(number of rows inΦ/number of columns inΦ).StOMP’s large-n performance exhibits two phases(success/failure) in this diagram,as does the performance of BP.The“success phase”(the region in the phase diagram where StOMP successfullyfinds sparse solutions)is large and comparable in size to the success phase for 1minimization.In a sense StOMP is more effective atfinding sparse solutions to large extremely under-determined problems than either 1minimization or OMP;its phase transition boundary is even higher at extreme sparsity than the other methods.Moreover,StOMP takes a few seconds to solve problems that may require days for 1solution.As a result StOMP is well suited to large-scale applications.Indeed we give several explicitly worked-out examples of realistic size illustrating the performance benefits of this approach.Our analysis suggests the slogannoiseless underdetermined problems behave like noisy well-determined problems,i.e.coping with incompleteness of the measurement data is(for‘randomΦ’)similar to coping with Gaus-sian noise in complete measurements.At each StOMP stage,the usual set of matchedfilter coefficients is a mixture of‘noise’caused by cross-talk(non-orthogonality)and true signal;setting an appropriate threshold,we can subtract identified signal,causing a reduction in cross-talk at the next iteration.This is more than a slogan;we develop a theoretical framework for rigorous asymptotic analysis.Theorems 1-3below allow us to track explicitly the successful capture of signal,and the reduction in cross-talk, stage by stage,rigorously establishing(asymptotic)success below phase transition,together with the failure that occurs above phase transition.The theory agrees with empiricalfinite-n results.Our paper is organized as follows.Section2presents background on the sparse solutions problem; Section3introduces the StOMP algorithm and documents its favorable performance;Section4develops a performance measurement approach based on the phase diagram and phase transition.Section5analyzes the computational complexity of the algorithm.Section6develops an analytic large-system-limit for predicting phase transitions which agree with empirical performance characteristics of StOMP.Section 7develops the Gaussian noise viewpoint which justifies our thresholding rules.Section8describes the performance of StOMP under variations[adding noise,of distribution of nonzero coefficients,of matrix ensemble]and documents the good performance of StOMP under all these variations.Section9presents computational examples in applications App1-App3that document the success of the method in simulated model problems.Section10describes the available software package which reproduces the results in this paper and Section11discusses the relationship of our results to related ideas in multiuser detection theory and to previous work in the sparse solutions problem.2Sparse Solution PreliminariesRecall the Sparse Solutions Problem(SSP)mentioned in the introduction.In the SSP,an unknown vector x0∈R N is of interest;it is assumed sparse,which is to say that the number k of nonzeros is much smaller than N.We have the linear measurements y=Φx0whereΦis a known n by N matrix, and wish to recover x0.Of course,ifΦwere a nonsingular square matrix,with n=N,we could easily recover x from y; but we are interested in the case where n<N.Elementary linear algebra tells us that x0is then not uniquely recoverable from y by linear algebraic means,as the equation y=Φx may have many solutions.However,we are seeking a sparse solution,and for certain matricesΦ,sparsity will prove a powerful constraint.Some of the rapidly accumulating literature documenting this phenomenon includes [21,20,32,55,56,50,51,8,18,16,57,58,48].For now,we consider a specific collection of matrices where sparsity proves valuable.Until we say otherwise,letΦbe a random matrix taken from the Uniform Spherical ensemble(USE);the columns of Φare iid points on the unit sphere S n−1[16,17].Later,several other ensembles will be introduced.3Stagewise Orthogonal Matching PursuitStOMP aims to achieve an approximate solution to y=Φx0whereΦcomes from the USE and x0is sparse.In this section,we describe its basic ingredients.In later sections we document and analyse itsMatched Filter"T r s Projection "I s T "I s ()#1"I s T y Interference Construction "x sFigure 1:Schematic Representation of the StOMP algorithm.performance.3.1The ProcedureStOMP operates in S stages,building up a sequence of approximations x 0,x 1,...by removing detected structure from a sequence of residual vectors r 1,r 2,....Figure 1gives a diagrammatic representation.StOMP starts with initial ‘solution’x 0=0and initial residual r 0=y .The stage counter s starts at s =1.The algorithm also maintains a sequence of estimates I 1,...,I s of the locations of the nonzeros in x 0.The s -th stage applies matched filtering to the current residual,getting a vector of residual correlationsc s =ΦT r s −1,which we think of as containing a small number of significant nonzeros in a vector disturbed by Gaussian noise in each entry.The procedure next performs hard thresholding to find the significant nonzeros;the thresholds,are specially chosen based on the assumption of Gaussianity [see below].Thresholding yields a small set J s of “large”coordinates:J s ={j :|c s (j )|>t s σs };here σs is a formal noise level and t s is a threshold parameter.We merge the subset of newly selected coordinates with the previous support estimate,thereby updating the estimate:I s =I s −1∪J s .We then project the vector y on the columns of Φbelonging to the enlarged support.Letting ΦI denote the n ×|I |matrix with columns chosen using index set I ,we have the new approximation x s supported in I s with coefficients given by (x s )I s =(ΦT I s ΦI s )−1ΦT I s y.The updated residual isr s =y −Φx s .We check a stopping condition and,if it is not yet time to stop,we set s :=s +1and go to the next stage of the procedure.If it is time to stop,we set ˆx S =x s as the final output of the procedure.Remarks:1.The procedure resembles Orthogonal Matching Pursuit(known to statisticians as Forward StepwiseRegression).In fact the two would give identical results if S were equal to n and if,by coincidence, the threshold t s were set in such a way that a single new term were obtained in J s at each stage.2.The thresholding strategy used in StOMP(to be described below)aims to have numerous termsenter at each stage,and aims to have afixed number of stages.Hence the results will be different from OMP.3.The formal noise levelσs= r s 2/√n,and typically the threshold parameter takes values in therange2≤t s≤3.4.There are strong connections to:stagewise/stepwise regression in statistical model building;succes-sive interference cancellation multiuser detectors in digital communications and iterative decoders in error-control coding.See the discussion in Section11.Our recommended choice of S(10)and our recommended threshold-setting procedures(see Section 3.4below)have been designed so that when x0is sufficiently sparse,the following two conditions are likely to hold upon termination:•All nonzeros in x0are selected in I S.•I S has no more than n entries.The next lemma motivates this design criterion.Recall thatΦis sampled from the USE and so columns ofΦare in general position.The following is proved in Appendix A.Lemma3.1Let the columns ofΦbe in general position.Let I S denote the support ofˆx S.Suppose that the support I0of x0is a subset of I S.Suppose in addition that#I S≤n.Then we have perfect recovery:ˆx S=x0.(3.1)3.2An ExampleWe give a simple example showing that the procedure works in a special case.We generated a coefficient vector x0with k=32nonzeros,having amplitudes uniformly distributed on[0,1].We sampled a matrixΦat random from the USE with n=256,N=1024,and computed a linear measurement vector y=Φx0.Thus the problem of recovering x0given y is1:4underdetermined (i.e.δ=n/N=.25),with underlying sparsity measureρ=k/n=.125.To this SSP,we applied StOMP coupled with the CFAR threshold selection rule to be discussed below.The results are illustrated in Figure2.Panels(a)-(i)depict each matchedfiltering output,its hard thresholding and the evolving approxi-mation.As can be seen,after3stages a result is obtained which is quite sparse and,as thefinal panel shows,matches well the object x0which truly generated the data.In fact,the error at the end of the third stage measures ˆx3−x0 2/ x0 2=0.022,i.e.a mere3stages were required to achieve an accuracy of2decimal digits.3.3Approximate Gaussianity of Residual MAIAt the heart of our procedure are two thresholding schemes often used in Gaussian noise removal.(N.B. at this point we assume there is no noise in y!)To explain the relevance of Gaussian‘noise’concepts, note that at stage1,the algorithm is computing˜x=ΦT y;this is essentially the usual matchedfilter estimate of x0.If y=Φx0and x0vanishes except in one coordinate,the matchedfilter output˜x equals x0perfectly.Hence z=˜x−x0is a measure of the disturbance to exact reconstruction caused by multiple nonzeros in x0.The same notion arises in digital communications where it is called Multiple-Access Interference(MAI)[60].Perhaps surprisingly-because there is no noise in the problem-the MAI in our setting typically has a Gaussian behavior.MoreFigure2:Progression of the StOMP algorithm.Panels(a),(d),(g):successive matchedfiltering outputs c1,c2,c3;Panels(b),(e),(h):successive thresholding results;Panels(c),(f),(i):successive partial solutions. In this example,k=32,n=256,N=1024.specifically,ifΦis a matrix from the USE and if n and N are both large,then the entries in the MAI vector z have a histogram which is nearly Gaussian with standard deviationσ≈ x0 2/√n.(3.2)The heuristic justification is as follows.The MAI has the formz(j)=˜x(j)−x0(j)=j=φj,φ x0( ).The thing we regard as‘random’in this expression is the matrixΦ.The termξjk ≡ φj,φk measures theprojection of a random point on the sphere S n−1onto another random point.This random variable has approximately a Gaussian distribution N(0,1n).ForΦfrom the USE,for a givenfixedφj,the differentrandom variables(ξjk :k=j)are independently distributed.Hence the quantity z(j)is an iid sum ofapproximately normal r.v.’s,and so,by standard arguments,should be approximately normal with mean 0and varianceσ2j=V ar[j= ξjx0( )]=(j=x0( )2)·V ar(ξj1)≈n−1 x0 22Settingσ2= x0 2/n,this justifies(3.2).Computational experiments validate Gaussian approximation for the MAI.In Figure3,Panels(a),(d),(g) display Gaussian QQ-plots of the MAI in the sparse case with k/n=.125,.1875and.25,in the Uniform Spherical Ensemble with n=256and N=1024.In each case,the QQ-plot appears straight,as the Gaussian model would demand.Through the rest of this paper,the phrase Gaussian approximation means that the MAI has an approximately Gaussian marginal distribution.(The reader interested in formal proofs of Gaussian approximation can consult the literature of multiuser detection e.g.[46,61,12];such a proof is implicitin the proofs of Theorems1and2below.The connection between our work and MUD theory will be amplified in Section11below).Properly speaking,the term‘MAI’applies only at stage1of StOMP.At later stages there is residual MAI,i.e.MAI which has not yet been cancelled.This can be defined asz s(j)=x0(j)−φT j r s/ P Is−1φj 22,j∈I s−1;Figure3:QQ plots comparing MAI with Gaussian distribution.Left column:k/n=.125,middle column:k/n=.1875,right column:k/n=.25.Top row:USE,middle row:RSE,bottom row:URP. The RSE and URP ensembles are discussed in Section8.The plots all appear nearly linear,indicating that the MAI has a nearly Gaussian distribution.the coordinates j∈I s−1are ignored at stage s-the residual in those coordinates is deterministically0.Empirically,residual MAI has also a Gaussian behavior.Figure4shows quantile-quantile plots for the first few stages of the CFAR variant,comparing the residual MAI with a standard normal distribution. The plots are effectively straight lines,illustrating the Gaussian ter,we provide theoretical support for a perturbed Gaussian approximation to residual MAI.3.4Threshold SelectionOur threshold selection proposal is inspired by the Gaussian behavior of residual MAI.We view the vector of correlations c s at stage s as consisting of a small number of‘truly nonzero’entries,combined with a large number of‘Gaussian noise’entries.The problem of separating‘signal’from‘noise’in such problems has generated a large literature including the papers[24,27,26,1,23,37],which influenced our way of thinking.We adopt language from statistical decision theory[39]and thefield of multiple comparisons[38]. Recall that the support I0of x0is being(crudely)estimated in the StOMP algorithm.If a coordinate belonging to I0does not appear in I S,we call this a missed detection.If a coordinate not in I0does appear in I S we call this a false alarm.The coordinates in I S we call discoveries,and the coordinates in I S\I0we call false discoveries.(Note:false alarms are also false discoveries.The terminological distinction is relevant when we normalize to form a rate;thus the false alarm rate is the number of false alarms divided by the number of coordinates not in I0;the false discovery rate is the fraction of false discoveries within I S.)We propose two strategies for setting the threshold.Ultimately,each strategy should land us in a position to apply Lemma3.1:i.e.to arrive at a state where#I S≤n and there are no missed detections. Then,Lemma3.1assures us,we perfectly recover:ˆx S=x.The two strategies are:•False Alarm Control.We attempt to guarantee that the number of total false alarms,across all stages,does not exceed the natural codimension of the problem,defined as n−k.Subject to this, we attempt to make the maximal number of discoveries possible.To do so,we choose a threshold so the False Alarm rate at each stage does not exceed a per-stage budget.•False Discovery Control.We attempt to arrange that the number of False Discoveries cannot exceedFigure4:QQ plots comparing residual MAI with Gaussian distribution.Quantiles of residual MAI at different stages of StOMP are plotted against Gaussian quantiles.Near-linearity indicates approximate Gaussianity.afixed fraction q of all discoveries,and to make the maximum number of discoveries possible subject to that constraint.This leads us to consider Simes’rule[2,1].The False Alarm Control strategy requires knowledge of the number of nonzeros k or some upper bound.False Discovery Control does not require such knowledge,which makes it more convenient for applications,if slightly more complex to implement and substantially more complex to analyse[1].The choice of strategy matters;the basic StOMP algorithm behaves differently depending on the threshold strategy,as we will see below.Implementation details are available by downloading the software we have used to generate the results in this paper;see Section10below.4Performance Analysis by Phase TransitionWhen does StOMP work?To discuss this,we use the notions of phase diagram and phase transition.4.1Problem Suites,Performance MeasuresBy problem suite S(k,n,N)we mean a collection of Sparse Solution Problems defined by two ingredients: (a)an ensemble of random matricesΦof size n by N;(b)an ensemble of k-sparse vectors x0.By standard problem suite S st(k,n,N)we mean the suite withΦsampled from the uniform spherical ensemble,with x0a random variable having k nonzeros sampled iid from a standard N(0,1)distribution.For a given problem suite,a specific algorithm can be run numerous times on instances sampled from the problem suite.Its performance on each realization can then be measured according to some numerical or qualitative criterion.If we are really ambitious,and insist on perfect recovery,we use the performancemeasure1{ˆxS =x0}.More quantitative is the 0-norm, ˆx S−x0 0,the number of sites at which the twovectors disagree.Both these measures are inappropriate for use withfloating point arithmetic,which does not produce exact agreement.We prefer to use instead 0, ,the number of sites at which the reconstruction and the target disagree by more than =10−4.We can also use the quantitative measure relerr2= ˆx S−x0 2/ x0 2,declaring success when the measure is smaller than afixed threshold(say ).For a qualitative performance indicator we simply report the fraction of realizations where the qual-itative condition was true;for a quantitative performance measure,we present the mean value across instances at a given k,n,N.Figure5:Phase Diagram for 1minimization.Shaded attribute is the number of coordinates of recon-struction which differ from optimally sparse solution by more than10−4.The diagram displays a rapid transition from perfect reconstruction to perfect disagreement.Overlaid red curve is theoretical curve ρ1.4.2Phase DiagramA phase diagram depicts performance of an algorithm at a sequence of problem suites S(k,n,N).The average value of some performance measure as displayed as a function ofρ=k/n andδ=n/N.Both of these variablesρ,δ∈[0,1],so the diagram occupies the unit square.To illustrate such a phase diagram,consider a well-studied case where something interesting happens. Let x1solve the optimization problem:(P1)min x 1subject to y=Φx.As mentioned earlier,if y=Φx0where x0has k nonzeros,we mayfind that x1=x0exactly when k is small enough.Figure5displays a grid ofδ−ρvalues,withδranging through50equispaced points in the interval[.05,.95]andρranging through50equispaced points in[.05,.95];here N=800.Each point on the grid shows the mean number of coordinates at which original and reconstruction differ by more than10−4,averaged over100independent realizations of the standard problem suite S st(k,n,N). The experimental setting just described,i.e.theδ−ρgrid setup,the values of N,and the number of realizations,is used to generate phase diagrams later in this paper,although the problem suite being used may change.This diagram displays a phase transition.For smallρ,it seems that high-accuracy reconstruction is obtained,while for largeρreconstruction fails.The transition from success to failure occurs at different ρfor different values ofδ.This empirical observation is explained by a theory that accurately predicts the location of the observed phase transition and shows that,asymptotically for large n,this transition is perfectly sharp. Suppose that problem(y,Φ)is drawn at random from the standard problem suite,and consider the event E k,n,N that x0=x1i.e.that 1minimization exactly recovers x0.The paper[19]defines a functionρ1(δ)(called thereρW)with the following property.Consider sequences of(k n),(N n)obeying k n/n→ρand n/N n→δ.Suppose thatρ<ρ1(δ).Then as n→∞P rob(E kn ,n,N n)→1.On the other hand,suppose thatρ>ρ1(δ).Then as n→∞P rob(E kn ,n,N n)→0.The theoretical curve(δ,ρ1(δ))described there is overlaid on Figure5,showing good agreement betweenasymptotic theory and experimental results.Figure6:Phase diagram for CFAR thresholding.Overlaid red curve is heuristically-derived analytical curveρF AR(see Appendix B).Shaded attribute:number of coordinates wrong by more than10−4 relative error.4.3Phase Diagrams for StOMPWe now use phase diagrams to study the behavior of StOMP.Figure6displays performance of StOMP with CFAR thresholding with per-iteration false alarm rate(n−k)/(S(N−k)).The problem suite and un-derlying problem size,N=800,are the same as in Figure5.The shaded attribute again portrays the number of entries where the reconstruction misses by more than10−4.Once again,for very sparse problems(ρsmall),the algorithm is successful at recovering(a good approximation to)x0,while for less sparse problems(ρlarge),the algorithm fails.Superposed on this display is the graph of a heuristically-derived functionρF AR,which we call the Predicted Phase transition for CFAR thresholding.Again the agreement between the simulation results and the predicted transition is reasonably good.AppendixB explains the calculation of this predicted transition,although it is best read only afterfirst reading Section6.Figure7shows the number of mismatches for the StOMP algorithm based on CFDR thresholding with False Discovery Rate q=1/2.Here N=800and the display shows that,again,for very sparse problems(ρsmall),the algorithm is successful at recovering(a good approximation to)x0,while for less sparse problemsρlarge,the algorithm fails.Superposed on this display is the graph of a heuristically-derived functionρF DR,which we call the Predicted Phase transition for CFDR thresholding.Again the agreement between the simulation results and the predicted transition is reasonably good,though visibly not quite as good as in the CFAR case.5ComputationSince StOMP seems to work reasonably well,it makes sense to study how rapidly it runs.5.1Empirical ResultsTable1shows the running times for StOMP equipped with CFAR and CFDR thresholding,solving an instance of the problem suite S st(k,n,N).We compare thesefigures with the time needed to solve the same problem instance via 1minimization and OMP.Here 1minimization is implemented using Michael Saunders’PDCO solver[49].The simulations used to generate thefigures in the table were all executed on a3GHz Xeon workstation,comparable with current desktop CPUs.Table1suggests that a tremendous saving in computation time is achieved when using the StOMP schemeover traditional 1minimization.The conclusion is that CFAR-and CFDR-based methods have a large。
网龙笔试范文您需要登录后才可以回帖登录 | 注册发布面试时，所问到的东西。
1.接口定义的规范是什么?2.stl中map的原理，和时间复杂度是什么?3.mfc中document类和view类联系4.函数重载5.函数覆盖，函数覆盖与虚函数之间的关系很久之前就听人建议c和c++精通一个就行，算法才是灵魂，而去网龙面试却问到这么多我不擅长的东西。
直接出局了。
由于个人原因，导致我丧失了一次一次机会，我也很是遗憾。
其实里面有些公司，还是很对我的胃口的。
还是静下心来，温习一下c++吧，毕竟以前也很常用，很容易就熟练了。
可惜c++需要记忆的东西太多。
这是我不喜欢它的原因之一。
可现在我又有什么别得选择呢，现在每一次机会，我都得把握住，否则真得失业了。
下面记录一下，我比较薄弱，或者说是我以前的知识漏洞吧!1.1 i/o,cin,cout略1.2 注释c++中的注释不可嵌套*/会出错，原因是，把识别为注释，而*/则是半个注释符，故语法错误。
1.4控制语句while (std::cin >> value);使用 istream 对象作为条件，结果是测试流的状态。
如果流是有效的(也就是说，如果读入下一个输入是可能的)那么测试成功。
遇到文件结束符或遇到无效输入时，如读取了一个不是整数的值，则istream 对象是无效的。
处于无效状态的 istream 对象将导致条件失败。
从键盘输入文件结束符：windows下ctrl+z unix下ctrl+d2.1c++ 是静态类型(statically typed)语言，在编译时执行类型检查。
一些程序设计语言，特别是 smalltalk 和 python，在运行时才检查语句中对象的类型。
基本内置类型:整数、浮点数、单个字符和布尔值的算术类型，void 的特殊类型.表示整数、字符和布尔值的算术类型合称为整型。
字符类型：单字节)，wchar_t(双字节)整形：short半字长，int字长，long一个或两个字长bool 类型表示真值 true 和 false，0为false,非零为true,占据一个字节在二进制表示中，计算机是无类型区别的。
COSI: Adding Constraints to the object-oriented paradigmThe Trans TeamSpace Telescope Science Institute, 3700 San Martin Drive, Baltimore, MD 21218I.OverviewTrans[1]is a Lisp system at the Space Telescope Science Institute(STScI)which is a key part of the proposal preparation ground system for the Hubble Space Telescope(HST).It was originally developed in the late‘80s using a mixture of procedural,and blackboard architectures.While the original application met its requirements and performed well for a number of years,the increasing complexity of the system and its changing role meant that it eventually needed to be reengineered. In developing a replacement we wanted a mechanism to manage the complex inter-dependencies between application objects in a dynamic system.To meet this need we developed the Constraint Sequencing Infrastructure(COSI)which supports a model of programming with methods as con-straints.COSI automatically tracks dependencies between object state and constraints,manages the relationships between objects,and executes constraints when necessary to ensure that the internal state of the system is consistent.COSI is implemented as a general purpose extension to CLOS via the Meta-Object Protocol (MOP)[2].It extends the object-oriented paradigm to add the notion of methods as constraints which can automatically rerun when their inputs change.II.MotivationTrans was originally designed as a batch system,taking as input a proposal specification and pro-ducing a detailed sequence of telescope activities that will achieve the specified observations.A proposal specification describes the observations that the user wants to perform in a relatively high level language and from this description,Trans produces a detailed schedule of spacecraft activities that will perform and support those observations.There is typically considerableflexi-bility in the details of this schedule and Trans attempts tofind a solution that will make the most efficient use of the telescope.Internally Trans used a scripted approach toflow of control with a predefined sequence of steps intended to reach afinal solution.Each step in such a sequence depends upon the results of pro-ceeding steps to provide their input.This isfine when the sequence of dependencies is relatively static,but it becomes extremely difficult to maintain when the dependencies change.If new requirements make a calculation dependent upon a later step in the sequence then the script must be rearranged and it proved extremely difficult to determine the correct order for the script due to the complexity of all the dependencies.The nature of the HST,and the ground system that supports its operation,is one of constant change.Trans is constantly being updated and enhanced to adapt to changes on the spacecraft (both planned and unplanned)and to maintain and update the capabilities provided by the ground system.This environment of continual change made Trans difficult to maintain with its existing architecture and we decided that we needed an architecture that would assist us in managing thedependencies in the system.While Trans has historically been a batch system,its role is expanding and it will soon become a component of an interactive graphical system.This system will allow a proposal to be developed incrementally which will therefore require Trans to build its solutions incrementally.In addition, Trans must be able to make efficient updates its internal state in responses to changes to existing inputs.The architecture that we developed solves both of these problems by automatically tracking the dependencies in the system and by rerunning code when necessary to maintain an internally con-sistent state.III.Concept: Methods as Constraintsi)Constraint SequencingIn order to address our concerns about the difficulty of managing code dependencies,and method sequencing within a complex dynamic system we developed the notion of“methods as con-straints” which allows the system itself to manage these issues.A constraint specifies some relationship between input and output parameters.In other words,it constrains its output to specific legal values based upon its input.Constraints are declarative and have an underlying propagation engine that applies the constraints to the current state of the sys-tem.If the inputs to a constraint change then the effect of that constraint must be propagated to its outputs, changing those outputs, which may in turn be inputs to other constraints.Consider,for example,three values:X,Y and Z where constraint C1implies B=A+10and con-straint C2implies C=B+5.If the value of A changes then C1must be applied which will change the value of B.As a result,C2must be applied to change the value of C.This propagation contin-ues until the state is consistent.In an object-oriented system such as Trans,many of the methods resemble constraints,but with no underlying propagation mechanism.Methods are used in such a system to create objects and to assign values to the slots of those objects and so on.The behavior of those methods depends upon the objects and slots to which they refer,but in order to keep the system consistent when its inputs change there must be explicit calls to methods that depend upon those input values.In such a system it can be difficult to manage the dynamic nature of the objects and their inter-dependencies.Decisions can impact parameters already computed for objects which has a ripple effect requiring anything derived from that value to be recomputed.Once the system is required to be interactive,or to be able to search for better solutions then the need to respond to change is even more clear.Normally the dependencies between objects must be handled explicitly by the programmer,but by viewing methods as constraints we can build a propagation engine that will automatically track the dynamic dependencies between objects and constraints and which can therefore propagate the effect of a change throughout the system by rerunning constraints as necessary.This simplifies the programming task by making the code more declarative and self contained.As a simple example from the HST domain,suppose that we define a class exposure with twoslots:filter,and duration,and that there exists a mechanism for traversing a sequence of these exposures:(defclass Exposure ()((filter :initform clear :reader Get-Filter)(duration :reader Get-Duration))(:metaclass Constraint-Sequencer))(defconstraint Set-Duration ((self Exposure))(setf (slot-value self ‘Duration)(case filter(filter1 10)(filter2 15)(filter3 20))))The Set-Duration constraint is a method that can set the duration of an exposure to a value that is consistent with thefilter for the exposure.If thefilter for the exposure can change,either through a change to the input value,or through an internal decision by the system,then the Set-Duration method must be rerun to ensure that the duration of the exposure is correct.This method is actually defined to be a constraint and as a result the underlying constraint mechanism is responsible for detecting dependencies and propagating changes through the system.In this case the Set-Duration constraint for a specific instance of exposure is dependent upon thefilter slot of that instance.If thefilter slot should change then the infrastructure is responsible for rerun-ning the dependent constraints for that instance.We believe that this provides a simpler,cleaner way of expressing the relationship between objects and object attributes.The notion of constraint makes the system more declarative by expressing the requirement upon the duration of an exposure in a way that is independent of any flow of control.The underlying propagation mechanism is responsible for detecting the depen-dency of the constraint on related objects and attributes,and for running the constraint when nec-essary to ensure that all objects have consistent state.A common mechanism that is analogous to this approach is the spreadsheet.When a user con-structs a spreadsheet he enters values into some of the cells,and formula into others.Those for-mula constrain the value of their associated cell,based upon the values in the cells to which they refer.If a change is made to an input value,or to a formula,then the change is propagated throughout the spreadsheet.Within this model of method as constraint,the constraints are like the formula of a spreadsheet and object slots are like the data cells.ii)Object ManagementUsing the notion of method as constraint leads to a system which can automatically track the object state that code depends upon,and can rerun the code when that state changes.This implies,however,that constraints may run an arbitrary number of times.A key to containing propagation is to detect*change*so the system must recognize when a constraint changes some state and when it does not.Recognizing changes to object slots is straight forward,but many constraints will also create new objects and in subsequent runs may create the same,additional,or fewer objects.When objects are instantiated by a subsequent run of a constraint it is desirable to have the instantiation return the same object rather than a new one.This is achieved through an object creation mechanism that uses a unique key to identify the object to be created.The underlying mechanism maintains a table of known objects,associated with unique keys,and when a request is received for a specific object the system can determine if that object already exists.If so,then the existing object is returned,otherwise a new object is cre-ated.If a constraint reruns,therefore,and recreates the same object as the previous run then there will be no net change to the internal state.Although constraints may recreate the same objects,it is also possible that they will not recreate objects that were created with the previous run.In this case the system should detect the change and remove the superfluous object(s) for the sake of efficiency.Extending our HST example,let us suppose that longer exposures require additional calibration activities.Specifically,exposures that have a duration greater than15sec require a calibration activity to immediately follow them:(defconstraint Create-Required-Calibration ((self Exposure)) (when (> (Get-Duration self) 15)(Set-Next self(ensure-instance‘Calibration ()))))In this case we have a new constraint that depends upon the duration of the exposure.As the dura-tion changes this constraint will need to rerun to determine whether or not the calibration is required.Successive runs of this constraint may or may not create the calibration.The use of the ensure-instance form means that each time this code creates the calibration it is same instance that is returned, and if the code does not create the calibration then the object is “cleaned up”. iii)Relationship ManagementMost of the relationships that we need to model in Trans are bidirectional and in order to manage the consistency of such bidirectional links in a constraint based programming model we devel-oped the notion of relationships.Extending our HST example again,let us assume that calibra-tions should be linked to any exposure that they could be used to calibrate.While exposures that are greater than15sec duration require a calibration,other exposures may use a subsequent cali-bration if one has already been created.(defconstraint Calibrates-Relationship ((self Calibration)) (let ((exposure (Find-Exposures-To-Calibrate self)))(Set-Relationship self ’Calibration-For exposures))) Relationships are inherently bidirectional and have arbitrary cardinality.This means that relation-ships form a link between two sets of objects,either of which may be a list or a single object,and the creation of a link is seen by objects in both sets.In the example above,the constraint is creat-ing a relationship called calibration-for from the instance of a calibration to all of the exposures that it can calibrate.The two directions of a relationship have different semantics and therefore they have different names with neither direction having any particular significance or precedence. In this case the reverse relationship might be called calibrates and as a result,each exposure in the relationship will now have its calibrates relationship pointing to the calibration object.This mechanism goes a long way towards managing the internal consistency of a set of object relationships as the bidirectional links will be kept consistent.Within a constraint based model, however,subsequent runs of a constraint may set up a relationship in a different manner than aprior run and in this case the system must maintain the consistency of the relationships as those relationships change.Suppose in our example that an exposure in the middle of a long sequence now has itsfilter changed,causing it to become longer and therefore requiring a calibration.The constraints will insert that calibration into the sequence which would make the new calibration the correct calibra-tion activity for some of the earlier exposures.When the calibrates-relationships constraint runs for the new calibration it will set the calibration-for relationship between that calibration and the suitable prior exposures.In order to maintain consistency in the relationships,the exposures which are now linked to the new calibration must be unlinked from the old one.As a result,the calibrates relationship for the early exposures points to the new calibration while the calibration-for relationship for the original calibration no longer points to those early exposures.IV.COSI Implementation: Adding Constraints to CLOSCOSI is implemented using the CLOS Meta-object Protocol(MOP)which allowed us to build this capability as a direct extension to the standard object-oriented programming model rather than as a separate layer on top of that model.This is important as it enables the system to detect slot access and change through all of the built in functions, methods and macros.The MOP provides developers with a mechanism to specialize the behavior of CLOS itself.This is possible because the elements of CLOS,including classes and methods,are themselves objects instantiated from classes that may be specialized and extended.Classes,for instances,are objects instantiated from a metaclass(i.e.a class that describes a class)and this allows a developer to sub-class the default metaclass and to use the new metaclass for his application classes.The behavior of CLOS is implemented via methods on metaclasses,so new metaclasses can extend or special-ize this behavior.The components of COSI build on the capabilities of each other with the constraint sequencing requiring the object manager,and the object manager requiring the relationship manager.Our implementation of the relationship manager will be therefore be presentedfirst,followed by the object manager and finally the constraint sequencer.i)Relationship ManagerRelationshipsRelationships are bidirectional links between objects whose integrity is automatically managed by the Relationship Manager.The role of the Relationship Manager is mainly to act as the repository of relationship data. A relationship is defined by the following attributes:A name for each ‘direction’ of the relationshipA default value for each direction (i.e. nil or unbound).There are two major components to the Relationship Manager,a new relationship-class meta-class,and the relationship-manager itself.The combination of these components manage the relationships between objects.Relationship ClassA new metaclass is defined as a sub-class to standard-class called relationship-class which willprovide any class instantiated from this metaclass with the ability to use relationships with its instances:(defclass Relationship-Class (Standard-Class)())Standard-class is the default metaclass for CLOS classes and by adding the relationship-class subclass we are creating a way to specialize the behavior of specific classes.The relationship-class metaclass provides two things to the classes that are instantiated from it. Those classes all have a relationships slot which is initialized with a hash-table,and methods are defined for that implement the protocol used to cooperate in the management of relationships.The relationships hash-table provides a storage mechanism based upon keyed look-up by relationship name which means that classes do not have to specify which relationships they will participate in. While this capability could clearly have been written without resorting to the MOP,the fact that we needed to hook into the relationships in the same way that we hook into slot access,made this approach consistent with the needs of the constraint sequencer.The use of a protocol that dele-gates the work to the class of the object makes the relationship manager extensible via the MOP. Define a RelationshipRelationships are defined using the defrelationship macro which includes the name of the rela-tionship and the name for the reverse relationship e.g.:(defrelationship forward-name reverse-name&key :forward-defaults-to-unbound:reverse-defaults-to-unbound))The relationship manager maintains the table of defined relationships which provides the mapping between the two names.This is implemented via two entries into a hash table,one for each name with the name as the key.The value in this hash table is the reverse name and the default value of the relationship. The default value for a relationship may be either nil or unbound.Create a RelationshipA relationship between objects is created with the set-relationship method which takes the objects that are related and the relationship name as arguments:(set-relationship objects relationship objects)Where objects may be a single object,or a list of objects.This method calls the relationship man-ager method set-relationship-using-rm with any single object parameter as a singleton list.The relationship manager is responsible for managing the bidirectional nature of the relationship and the many-to-many nature of any links:(defmethod Set-Relationship-Using-RM((self Relationship-Manager)objects relationship related-objects)(let ((reverse-relationship(Reverse-Relationship self relationship)))(dolist (object objects)(Set-Single-Relationship-Using-RMself object relationship related-objects))(dolist (relative related-objects)(Set-Single-Relationship-Using-RMself relative reverse-relationship objects))))The relationship manager looks up the reverse relationship name and then iterates over each list of objects.For each object the method set-single-relationship-using-rm removes the object from any relationship it is currently in of that name,and then calls set-relationship-using-class on the class of the object to actually record the new relationship:(defmethod Set-Relationship-Using-Class((self Relationship-Class)object relationship related-objects)(setf (gethash relationship(Get-Relationship-Table object))related-objects))Note that this is a method on the relationship-class metaclass.Instances of classes of this meta-class all have a relationship table that stores the relationships for the object.Accessing RelationshipsA relationship is accessed using get-relationship which takes the object and relationship name as arguments:(get-relationship object relationship)This methodfirst calls get-relationship-using-rm which looks up the default value for the rela-tionship:(defmethod Get-Relationship-Using-RM((self Relationship-Manager) object relationship) (with-slots (default-to-unbound-table) self(Get-Relationship-Using-Class(clos::std-instance-class object) object relationship(gethash relationship default-to-unbound-table))))This method is responsible for looking up the default value for the relationship,forfinding the class of the object and for calling get-relationship-using-class on that class.This method looks up the related objects from the relationships hash table in the object using the relationship name as key.If there is no entry in the hash table then the default behavior is used which either returns nil, or throws an unbound-slot condition:(defmethod Get-Relationship-Using-Class((self Relationship-Class)object relationship default-to-unbound) (multiple-value-bind (value boundp)(gethash relationship (Get-Relationship-Table object)) (cond (boundp value)(default-to-unbound (error 'unbound-slot))(t nil))))Note again that this is a method on the relationship-class metaclass.ii)Object ManagerThe object manager handles the creation and deletion of objects based upon a unique key within a specific defined context,also identified by a unique key.It also uses relationships to track which objects create other objects with a parent/child relationship.Object Manager functionality is supported by a pair of macros:ensuring-instances and ensure-instance.The former is used to define the context for a set of objects created together,while the second is used to create a single object within that context.Object creation context is necessary to define the scope within which an associated set of objects are created.If objects were previously instantiated within a context and during a subsequent run any of those objects are not recreated,then the system must clean up the objects.The most impor-tant clean up action is to remove such objects from any relationships in which they participate. Object Creation ContextEnsuring-instances is the public interface to the object manager which defines the context for the creation of a group of objects.This context is important as it is used to determine when previously created objects must be deleted.Objects that are created on one pass through this context,but which are not recreated on the next pass are deleted.An object creation context is defined by an object table and a parent object.Ensuring-instances is used to define the scope of that context and may be passed an optional key or parent.Either may be explicitly specified or left implicit.If no key is given then a unique key is constructed during macro expansion.If no parent is defined then the objects created in this context will have no par-ent:(defmacro Ensuring-Instances ((&key key parent) &body body) `(apply #'values(unwind-protect(progn(Start-Object-Creation,(or key `',(gensym "OM-Key")) ,parent)(multiple-value-list (progn ,@BODY)))(Stop-Object-Creation))))The key is used to determine which object table applies in this context.The object manager main-tains a hash table which stores all of the object tables,referenced by their associated key.Start-object-creation uses this key to create a new object creation context and push it onto a stack: (defun Start-Object-Creation (key parent)(let* ((table (or (gethash key *OBJECT-TABLES*)(make-hash-table :test #'equalp))) (current-parent (or parent (default-parent)))(context (make-instance 'object-creation-context:current-object-table table:current-parent current-parent))) (push-object-creation-context context)(setf (gethash key *OBJECT-TABLES*) current-table)))The object creation context contains a table of objects,and the parent for any new objects.Stop-object-creation is used to perform clean up of any objects that are no longer required,and to then pop the context off the stack.Object CreationEnsure-instance is similar to the CLOS make-instance in syntax and is intended to be its analog. The only addition is an optional key which should uniquely identify the occurrence of ensure-instance within the current object creation context.If no key is supplied then the macro creates a unique key,during macro expansion.This key will be adequate if the ensure-instance form will only created one object in any context but this is often not the case and a key will need to be spec-ified.If the call is within any looping construct it will be used a number of times at each call will be expected to create a different object.(defmacro Ensure-Instance (type (&key key) &rest initargs)`(Ensure-Object,type,(or key `',(gensym "EI-Key")),@initargs))Ensure-object takes the given key and uses it as a reference into the object table associated with the current object creation context.If an object has previously been created with the key in this context then the object will be in the table and that object will be returned.If no object is found then a new instance is created and put into the table.In either case,any initialization parameters are applied to the instance which may, or may not, change slot values for an existing object: (defun Ensure-Object (type key initargs)(let* ((table (Get-Table *CURRENT-CONTEXT*))(object (gethash key table)))(cond (object(change-class object type)(apply #'Initialize-Instance object initargs))(t(setq object(apply #'Make-Instance type initargs))))(setf (gethash key table) object)(add-new-object object)object))The add-new-object call records which objects are created while a specific context is current which allows the system to clean up superfluous objects.Object DeletionDeletion means different things to different classes and we therefore defined a delete-object method which calls delete-object-using-class with the class of the object:(defmethod Delete-Object ((self Standard-Object))(Delete-Object-Using-Class(clos::std-instance-class self) self))The default implementation of delete-object-using-class,for standard-class,does very little,but is extended for classes of the relationship-class to remove the object from any relationships itcurrently participates in.iii)Constraint SequencingIn order to support our constraint based programming model,COSI dynamically monitors the execution of constraints.It detects slot access and slot changes by specializing the associated methods for a new metaclass which is defined as a subclass of relationship-class: (defclass Constraint-Sequencer (Relationship-Class)())This new metaclass is used to extend the default behavior of slot read and write methods and also to add two COSI specific slots to instances of classes of constraint-sequencer.These slots are called dependencies and invocations and they are used by COSI to record constraint invocations for an object, and to record which slots those invocations are dependent upon.Defining ConstraintsConstraints are defined using the defconstraint macro which has a similar syntax to defmethod but is restricted to a single parameter which must be typed:(defmacro DefConstraint (name parameter &body body)`(defmethod ,name (,(first parameter))(push (get-invocation ,(caar parameter) ',name)*CALL-STACK*)(catch 'constraint-exit(handler-bind((error #'Constraint-Condition-Handler))(Ensuring-Instances(:key (first *CALL-STACK*):parent ,(caar parameter))(progn ,@body))))(pop *CALL-STACK*)nil))This macro adds functionality around the body of the method itself.Prior to the execution of the body of the method it obtains an invocation for this constraint from the object itself,and pushes that invocation onto a stack.After the body of the method is complete this invocation is popped off of the stack.The macro also adds a condition handler around the body of the method and sets up an object cre-ation context for the constraint invocation.InvocationsAn invocation is the application of a constraint to a specific object.COSI has invocation instances that are created thefirst time a constraint is run for an object.The objects themselves are used to store their invocations in a hash table,indexed by constraint name.The get-invocation method is used to check for an entry in this table.If no invocation is found one is created and put into the table.。
